堆的实现【C++】

概念

介绍堆之前得说一下二叉树，由于堆的逻辑布局是二叉树，二叉树的树的子集，树只有一个根节点，向下衍生出了很多节点，而且这个节点之间相互没有连接，除非是父子节点，如果有连接了那就是图；如果拥有很多独立不连接的树，如许的数据布局称之为丛林。
如果对树作进一步的限定：每一个节点（包括根节点）最多只有两个子树，那么如许的树叫做二叉树，比如：

这种也是：

二叉树呢又可以分为完全二叉树和满二叉树：
完全二叉树就是每一个节点都有两个子树（子节点），例如：

满二叉树就是除了最后一层，也就是最底下的一层，其他的每层都是完全二叉树，而且最后一层的节点得从左到右存在，下面这种就属于满二叉树：

但是这种就不属于满二叉树：

堆的逻辑数据布局就是使用满二叉树实现的，为什么说是逻辑呢？这是由于我们在实际实现的时候使用的是数组来实现的，原因如下:
如果我们想使用数组来存储下面这个二叉树：

如许对吗？像如许写的话，岂不是没有二叉树的特点了，比如怎么判定左右子树呢？以是我们得从上到下，从左到右的添加进数组。

例如：

如许就可以轻松知道左右子树从而通过数组构建出二叉树了，但是这个数组的中央浪费了不少空间，怎样避免呢？
那就是使用满二叉树。
数组中的恣意一个节点怎么能够得到他的左右子节点和父节点呢？可以通过下面的几个公式：
如果想知道数组arr里面的节点i的左右子节点和父节点：

• 父节点=arr[(i-1)/2]
  
• 左节点=arr[i*2+1];
  
• 右节点=arr[i*2+2];
  

概念说完了，我们接下来可以用这种数据布局来构建一个大堆和小堆，大堆的特点是父节点肯定大于子节点，但是左右节点没有讲求，小堆则相反。
使用巨细堆可以实现topk题目，也就是求出一堆数据中第几大（小）的数是哪一个。也可以实现堆排序。
实现

先实现一个大堆：

然后就得插入数据：

每次插入数据都是插入到数组的最后面，也就是二叉树的最下一层的最右边，此时需要维护大堆的规则，也就是父节点的值大于子节点的值，由于每次插入时都是在最下面，以是如果不符合规则，当前插入的值大于父节点，我们就使用adjustUp函数举行向上调整。如下：

1. void Heap::adjustUp()
2. {
3.         int curIndex = _heap.size() - 1;
4.         while (curIndex > 0)
5.         {
6.                 int parentIndex = (curIndex - 1) / 2;
7.                 if (_heap[parentIndex] < _heap[curIndex])
8.                 {
9.             std::swap(_heap[parentIndex], _heap[curIndex]);
10.             curIndex = parentIndex;
11.                 }
12.                 else
13.                 {
14.                         break;
15.                 }
16.         }
18. }

复制代码

写一下测试跑跑看吧：

1. #include "heap.h"
3. int main() {
5.     Heap heap;
6.     heap.insert(1);
7.     heap.insert(2);
8.     heap.insert(3);
9. }

复制代码

喔吼！拿不到数组的值，我们要得到堆顶的值，那就写一个吧：

1. int Heap::top()
2. {
3.         if (_heap.size() > 0)
4.         {
5.                 return _heap[0];
6.         }
7.       
8. }

复制代码

运行得到：

可以看到堆顶的数据3，数组下标0处的数据是3，可以我们在插入的时候，0处一开始插入的是1，但是结果是3，这就说明没有题目。
如果要实现topk题目，我们需要每次都将堆顶的元素给删除了，如果求第3大的数，我们就删除两次，然后此时堆顶的元素就是第3大的数了下面我们来实现删除功能：
在数组中如果直接删除下标0处的元素，在举行调整，如许会需要变动整个数组，效率低下；因此，我们选择将下标0处的元素与最后一个元素交换，然后直接删除最后一个元素，在举行向下调整即可：

1. void Heap::pop()
2. {
3.         if (_heap.size() > 0)
4.         {
5.                 std::swap(_heap[0], _heap[_heap.size() - 1]);
6.         _heap.pop_back();
7.                 adjustDown();
8.         }
9. }
11. void Heap::adjustDown()
12. {
13.         int size = _heap.size();
14.         int curIndex = 0, leftIndex = 1;
16.         while (leftIndex < size)
17.         {
18.                 if (leftIndex + 1 < size && _heap[leftIndex] < _heap[leftIndex + 1])
19.                 {
20.                         leftIndex++;
21.                 }
23.                 if (_heap[curIndex] < _heap[leftIndex])
24.                 {
25.             std::swap(_heap[curIndex], _heap[leftIndex]);
26.                         curIndex = leftIndex;
27.                         leftIndex = curIndex * 2 + 1;
28.                 }
29.                 else
30.                 {
31.                         break;
32.                 }
33.         }
34.        
35. }

复制代码

在adjustDown这个函数中，使用leftIndex + 1 < size && _heap[leftIndex] < _heap[leftIndex + 1]来判定左右节点哪一个更大一些，然后用较大值和父节点的值举行比较，如果父节点的值小于子节点的值，那么就要向下调整，也就是需要交换，之后更新当前的父节点和左节点，再次举行判定。
下面举行测试：

结果也没有题目。
然后我们根据这个举行堆排序的编写：
测试代码如下：

1. int main() {
2.     srand((unsigned int)time(NULL));
3.     std::vector<int> v;
4.     for (int i = 0; i < 100; i++)
5.     {
6.         v.push_back(rand()%100);
7.     }
9.     Heap heap;
10.     heap.sort(v);
12.     for (auto& e : v)
13.     {
14.         std::cout << e << " ";
15.     }
16. }

复制代码

结果也没有题目。
完整代码

1. //heap.h
2. #pragma once
3. #include <vector>
4. #include <iostream>
5. #include <cassert>
7. class Heap {
8. public:
9.         Heap();
10.         ~Heap();
12.     void insert(int value);
13.         void adjustUp();
14.         int top();
15.         void pop();
16.         void adjustDown();
17.         void sort(std::vector<int>& v);
18. private:
19.         std::vector<int> _heap;
20. };

复制代码

1. //heap.cpp
2. #include "heap.h"
4. Heap::Heap()
5. {
9. }
13. Heap::~Heap()
14. {
16. }
18. void Heap::insert(int value)
19. {
20.         _heap.push_back(value);
21.         adjustUp();
22. }
25. void Heap::adjustUp()
26. {
27.         int curIndex = _heap.size() - 1;
28.         while (curIndex > 0)
29.         {
30.                 int parentIndex = (curIndex - 1) / 2;
31.                 if (_heap[parentIndex] < _heap[curIndex])
32.                 {
33.                         std::swap(_heap[parentIndex], _heap[curIndex]);
34.                         curIndex = parentIndex;
35.                 }
36.                 else
37.                 {
38.                         break;
39.                 }
40.         }
42. }
45. int Heap::top()
46. {
47.         if (_heap.size() > 0)
48.         {
49.                 return _heap[0];
50.         }
52. }
54. void Heap::pop()
55. {
56.         if (_heap.size() > 0)
57.         {
58.                 std::swap(_heap[0], _heap[_heap.size() - 1]);
59.                 _heap.pop_back();
60.                 adjustDown();
61.         }
62. }
64. void Heap::adjustDown()
65. {
66.         int size = _heap.size();
67.         int curIndex = 0, leftIndex = 1;
69.         while (leftIndex < size)
70.         {
71.                 if (leftIndex + 1 < size && _heap[leftIndex] < _heap[leftIndex + 1])
72.                 {
73.                         leftIndex++;
74.                 }
76.                 if (_heap[curIndex] < _heap[leftIndex])
77.                 {
78.             std::swap(_heap[curIndex], _heap[leftIndex]);
79.                         curIndex = leftIndex;
80.                         leftIndex = curIndex * 2 + 1;
81.                 }
82.                 else
83.                 {
84.                         break;
85.                 }
86.         }
87.        
88. }
90. void Heap::sort(std::vector<int>& v)
91. {
92.         for (int i = 0; i < v.size(); i++)
93.         {
94.         insert(v[i]);
95.         }
96.     for (int i = 0; i < v.size(); i++)
97.     {
98.         v[i] = top();
99.         pop();
100.     }
101. }

复制代码

1. //main.c
2. #include "heap.h"
3. #include <ctime>
5. int main() {
7.     /*Heap heap;
8.     heap.insert(1);
9.     heap.insert(2);
10.     heap.insert(3);
11.     heap.pop();
12.     std::cout << heap.top() << std::endl;
13.     heap.pop();
14.     std::cout << heap.top() << std::endl;*/
16.     srand((unsigned int)time(NULL));
17.     std::vector<int> v;
18.     for (int i = 0; i < 100; i++)
19.     {
20.         v.push_back(rand()%100);
21.     }
23.     Heap heap;
24.     heap.sort(v);
26.     for (auto& e : v)
27.     {
28.         std::cout << e << " ";
29.     }
30. }

复制代码

---

            新人创作不易，你的点赞和关注都是对我莫大的鼓励，再次感谢您的观看。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。