C++数据结构之：堆Heap

摘要：

  it人员无论是使用哪种高级语言开发东东，想要更高效有层次的开发程序的话都躲不开三件套：数据结构，算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。
  此系列专注讲解数据结构数组、链表、队列、栈、树、哈希表、图，通过介绍概念以及提及一些可能适用的场景，并以C++代码简易实现，多方面认识数据结构，最后为避免重复造轮子会浅提对应的STL容器。本文介绍的是堆Heap。

（开发环境：VScode，C++17）

关键词： C++，数据结构，堆，Heap

声明：本文作者原创，转载请附上文章出处与本文链接。

正文：

介绍：

  堆比较特殊，通常被看作一棵完全二叉树的数组对象。被用于实现“优先队列”(priority queues)，优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺 序取出。在堆的树形结构中，各个顶点被称为“结点”(node)，数据就存储在这些结点中。

  上面叫大顶堆，如果每一个节点小于子树中每个节点的值，那就叫小顶堆。

特性：

只要满足下面两个特点的树形结构就是堆：

• 堆是一个完全二叉树（所谓完全二叉树就是除了最后一层其他层的节点个数都是满的）。
• 堆中每一个节点的值都必须大于（大顶堆/最大堆）等于或者小于（小顶堆/最小堆）其子树中每一个节点的值。

应用：

• 堆排序：堆排序是一种基于堆的排序算法，利用最大堆（或最小堆）的性质来排序数据，时间复杂度为O(n log n)，且不需要额外的存储空间，是一种非常高效的排序方法。
• 图算法：在许多图算法中，如计算最短路径的Dijkstra算法和构建最小生成树的Prim算法，堆被用作优先队列来选择下一个要处理的顶点。
• 动态数据流的中值查找：堆可以用来快速计算动态数据流的中值或其他顺序统计量。
• 带权调度问题：在处理带权任务调度问题时，可以使用最小堆来安排任务的执行顺序，以最小化等待时间或优化其他指标。
• Top K问题：堆经常用于解决Top K问题，即从一组数据中找到最大或最小的K个元素。
• 频率统计和数据压缩：在频率统计和数据压缩领域，如Huffman编码算法，使用最小堆来构建Huffman树，以实现高效的编码方案。

代码实现：

#ifndef CHEAP_H
#define CHEAP_H
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>

using namespace std;
template <typename T>
class MaxHeap
{
public:
	void heapify(int i);							// 辅助函数：调整堆  
    void push(const T& element); 					// 添加元素到堆中
    T pop();										// 移除并返回堆顶元素  
  
    T top() const; 									// 返回堆顶元素
    bool empty() const { return heap.empty(); }  	// 检查堆是否为空  
    size_t size() const { return heap.size(); }   	// 返回堆的大小  

private:
    vector<T> heap;
};

template <typename T>
inline void MaxHeap<T>::heapify(int i)
{
	int left = 2 * i + 1;
	int right = 2 * i + 2;
	int largest = i;
	if (left < heap.size() && heap[left] > heap[largest]) {
		largest = left;
	}
	if (right < heap.size() && heap[right] > heap[largest]) {
		largest = right;
	}
	if (largest != i) {
		swap(heap[i], heap[largest]);
		heapify(largest); // 递归调整子堆
	}
}

template <typename T>
inline void MaxHeap<T>::push(const T &element)
{
	heap.push_back(element);
	// 从新添加的节点开始向上调整堆
	int i = heap.size() - 1;
	while (i > 0 && heap[(i - 1) / 2] < heap[i]) { 
		swap(heap[i], heap[(i - 1) / 2]);
		i = (i - 1) / 2;
	}
}

template <typename T>
inline T MaxHeap<T>::pop()
{
    if(heap.empty())
		return T();
	T top = heap[0];
	heap[0] = heap.back();
	heap.pop_back();

	// 从堆顶开始向下调整堆
	heapify(0);
	return top;
}

template <typename T>
inline T MaxHeap<T>::top() const
{
	if(heap.empty())
		return T();
	return heap[0];
}

#endif // !CHEAP_H
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include "cheap.h"
using namespace std;

int main() 
{
    MaxHeap<int> maxHeap;
    maxHeap.push(20);
    maxHeap.push(18);
    maxHeap.push(15);
	maxHeap.push(8);
	maxHeap.push(10);
	maxHeap.push(5);
	maxHeap.push(3);
    cout << "Top element: " << maxHeap.top() << endl;
    maxHeap.pop();
    cout << "Top element after pop: " << maxHeap.top() << endl;
    return 0;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

对应STL：

• priority_queue：

  priority_queue 默认在 vector 上使用堆算法将 vector 中元素构造成大顶堆的结构，用户也可以通过自定义模板参数中的 class Compare 来实现一个小顶堆。因此 priority_queue 就是堆 ，所有需要用到堆的位置，都可以考虑使用 priority_queue。

推荐阅读

C/C++专栏：https://blog.csdn.net/weixin_45068267/category_12268204.html
（内含其它数据结构及对应STL容器使用）