堆与优先级队列：算法高效利器

堆(heap)实际就是完全二叉树，但他的结点的值有两种趋势，一是从根节点的值到叶子节点的值从小到大称为小根堆，从根节点的值从大到小称为大根堆，否则不是堆。

当堆中插入数据或删除数据时，有向上调整算法和向下调整算法。

向上调整算法：当堆中插入数据，放在末尾，再逐渐向上调。以大根堆举例：

1：插入点与父节点的值比较，若是该点值大于父节点值，则交换。

2：重复1操作，直到小于父节点的值或交换到根节点为止。

void up(int child) { int parent = child / 2; while (parent >= 1 && heap[parent] <= heap[child]) { swap(heap[parent], heap[child]); child = parent; parent = child / 2; } }

向下调整算法：用于删除堆顶元素，堆排序的堆操作。以大根堆举例

1：找到左右孩子节点中值最大的节点，若该节点值小于孩子中值最大的节点，二者交换。

2：重复1操作，直到该点的值比两个孩子节点的值多大或换到叶子节点为止。

void down(int parent) { int child = parent * 2; while (child <= n) { if (child + 1 <= n && heap[child + 1] >= heap[child]) { child++; } if (heap[child] <= heap[parent]) { return; } swap(heap[child], heap[parent]); parent = child; child = parent * 2; } }

时间复杂度为O(logN)。

堆模拟实验：创建一个堆后，插入元素，然后执行向上调整算法：

void up(int child)//向上调整算法 { int parent = child / 2; while (parent >= 1 && heap[parent] <= heap[child]) { swap(heap[parent], heap[child]); child = parent; parent = child / 2; } } void push(int num)//插入元素 { heap[++n] = num; up(num); }

执行堆的删除元素：

void down(int parent)//向下调整算法 { int child = parent * 2; while (child <= n) { if (child + 1 <= n && heap[child + 1] >= heap[child]) { child++; } if (heap[child] <= heap[parent]) { return; } swap(heap[child], heap[parent]); parent = child; child = parent * 2; } } void pop(int num)//删除元素 { swap(heap[1], heap[n]); n--; down(1); }

根据以上内容我们大致了解了堆的基本概念和内容，接下来再衔接优先级队列priority_queue就简单许多。

priority_queue实际上可以近似认为是堆的数据结构，在普通的队列是先进先出，优先级队列也是如此，但它会根据元素的优先级自动排序，优先级最高的最先被删除。

它有许多便利的函数：

#include <iostream> #include <queue> using namespace std; priority_queue<int>heap; int main() { for (int i = 1; i <= 10; i++) { heap.push(i);//时间复杂度为O(logN). } int t = heap.top();//时间复杂度为O(1). heap.pop();//时间复杂度为O(logN). int m = heap.size();//时间复杂度为O(1). if (heap.empty())//时间复杂度为O(1). { cout << 1 << endl; } return 0; }

（其中函数的时间复杂度在注释中）

优先级队列中含有内置类型和结构体类型，正常创建时默认为大根堆

priority_queue<int>heap;//默认为大根堆

如果需要变为小根堆请看代码：

priority_queue<int, vector<int>, less<int>>heap1;//大根堆 priority_queue<int, vector<int>, greater<int>>heap2;//小根堆

结构体类型的模拟相对复杂，还需要用operator的重载运算符，需要在结构体内部来定义大小堆：

struct node { int ans; bool operator <(const node& x)const//利用operator的重载运算符'<'来定义 { return ans < x.ans;//如果是'<'就是大根堆，是'>'就是小根堆 } }; priority_queue<node>heap;

以上就是堆和优先级队列的全部内容，如果在算法题中若是观察到有单调性的题目，我们可以在被时间复杂度限制时，运用以上内容。

完结撒花!!!