Previous
树结构算法总结(1) 二叉树的遍历
树结构算法总结(2) 线段树Segment Tree
树结构算法总结(3) 字典树Trie Tree
树结构算法总结(4) 堆Heap
堆的概念和建立
概念
我们这里说的堆和内存机制里的堆（内存机制的堆更偏向于链表结构）不一样。数据结构的堆其实是一种排序的完全二叉树（不一定是满二叉树）。对每个节点，它的孩子节点都比它大（最小堆），且堆顶元素是最小值；或者都比它小（最大堆），且堆顶元素是最大值。因此我们可以通过堆来做如下事情：
- 排序
- 查找第k个大的数
- 其他
以下引用自lintcode的简单说明：
什么是堆？
堆是一种数据结构，它通常有三种方法：push， pop 和 top。其中，“push”添加新的元素进入堆，“pop”删除堆中最小/最大元素，“top”返回堆中最小/最大元素。
什么是堆化？
把一个无序整数数组变成一个堆数组。如果是最小堆，每个元素A[i]，我们将得到A[i * 2 + 1] >= A[i]和A[i * 2 + 2] >= A[i]
如果有很多种堆化的结果？
返回其中任何一个。
堆化
时间复杂度：O(n)
思路
自下向上对树进行堆排序。当某个节点调整过（比如左孩子和父节点交换，或者右孩子和父节点交换），则需要对该节点（左孩子或右孩子）为根节点的子树进行重新堆排序。
实现
# 最大堆
class Solution {
public:
/**
* @param A: Given an integer array
* @return: void
*/
void heapify(vector<int> &A) {
// write your code here
heap(A, A.size()-1);
}
void heap(vector<int>& A, int m){
for(int i=m/2;i>=0;i--){
int cur = 2*i+1;
while(cur<A.size()){
if(cur+1<A.size()&&A[cur]<A[cur+1])
cur++;
if(A[cur]>A[(cur-1)/2]){
swap(A[cur], A[(cur-1)/2]);
cur = 2*cur+1;
}
else
break;
}
}
}
};
# 最小堆
class Solution {
public:
/**
* @param A: Given an integer array
* @return: void
*/
void heapify(vector<int> &A) {
// write your code here
heap(A, A.size()-1);
}
void heap(vector<int>& A, int m){
for(int i=m/2;i>=0;i--){
int cur = 2*i+1;
while(cur<A.size()){
if(cur+1<A.size()&&A[cur]>A[cur+1])
cur++;
if(A[cur]<A[(cur-1)/2]){
swap(A[cur], A[(cur-1)/2]);
cur = 2*cur+1;
}
else
break;
}
}
}
};
堆的应用
排序矩阵中的从小到大第k个数
在一个排序矩阵中找从小到大的第 k 个整数。
排序矩阵的定义为：每一行递增，每一列也递增。
给出 k = 4 和一个排序矩阵：
[
[1 ,5 ,7],
[3 ,7 ,8],
[4 ,8 ,9],
]
返回 5。
思路
考虑第k个，且矩阵排序，则这个元素一定在(i+1)*(j+1)范围里，因此缩小了遍历空间。之后将每个元素存入优先队列（下面有说明）中，且保持优先队列中的元素个数为k个，一旦有比优先队列中最大值小的元素，则将该元素放入队列中，并pop出最大值元素。这样最后只要输出优先队列的最大值即为从小到大第k个数。
实现
class Solution {
public:
/**
* @param matrix: a matrix of integers
* @param k: an integer
* @return: the kth smallest number in the matrix
*/
struct comp{
bool operator() (int a, int b){
return a<b;
}
};
int kthSmallest(vector<vector<int> > &matrix, int k) {
// write your code here
priority_queue<int, vector<int>, comp> pq;
int m = matrix.size();
if(m<1)
return 0;
int n = matrix[0].size();
for(int i=0;i<m;i++){
for(int j=0;j<n&&(i+1)*(j+1)<=k;j++){
if(pq.size()<k)
pq.push(matrix[i][j]);
else{
if(pq.top()>matrix[i][j]){
pq.pop();
pq.push(matrix[i][j]);
}
else
break;
}
}
}
return pq.top();
}
};
说明
priority_queue是C++里一种优先队列的数据结构。它的模板定义如下：
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
上面的T，对应题目的int，表示存储的元素为int；上面的Container，对应题目的vector
比较器的说明：
priority_queue默认使用最大堆的方式，对应的比较器为less（即a<b），最大的元素排在队列前面。当使用pq.top()时，访问的是队列头元素。
比较器是用于比较两个元素的大小或其它性质的逻辑判断，用于队列里的元素排序。
具体可以参考：cplusplus.priority_queue
合并k个排序链表
合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度。
给出3个排序链表[2->4->null,null,-1->null]，返回 -1->2->4->null
思路
先把所有的链表元素进行堆排序，之后直接输出每个元素，并把它们串起来。
实现
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
ListNode *mergeKLists(vector<ListNode *> &lists) {
// write your code here
vector<ListNode *> res;
for(auto link:lists){
while(link){
res.push_back(link);
link = link->next;
}
}
if(res.empty())
return NULL;
auto f = [](ListNode* a, ListNode* b){return a->val>b->val;};
make_heap(res.begin(), res.end(), f);
ListNode* head = res[0];
pop_heap(res.begin(), res.end(), f);
res.pop_back();
ListNode* h = head;
while(!res.empty()){
head->next = res[0];
pop_heap(res.begin(), res.end(), f);
res.pop_back();
head = head->next;
}
return h;
}
};
说明
-
auto f = [](ListNode* a, ListNode* b){return a->val>b->val;};对应的是比较器，只不过这里我们使用函数指针来代替。 make_heap、push_heap、pop_heap、sort_heap都是默认按最大堆排序。make_heap：进行堆化(最大元素在开头)；push_heap：如果有新元素加入，则需要使用push_heap（一般要先push元素，再用该命令）；pop_heap：如果要删除元素，则使用该命令（一般先用该命令，再pop掉元素）；sort_heap：直接进行堆排序，默认为从小到大；- 操作后三个命令之前，必须要进行一次make_heap(初始化的时候用就可以了)。
- 上面四个命令和priority_queue（大致）等价。
- 具体参考：make_heap