天津移动网站设计,wordpress中科大字体,四川大学规划建设处官方网站,四川住房建设厅网站增项查询今天来讲一下堆#xff0c;在网上看到一个很好的文章#xff0c;不过它实现堆是用Golang写的#xff0c;我这里打算用C实现一下#xff1a;
Golang: Heap data structure
1. 基本概念
满二叉树#xff08;二叉树每层节点都是满的#xff09;#xff1a; 完全二叉树在网上看到一个很好的文章不过它实现堆是用Golang写的我这里打算用C实现一下
Golang: Heap data structure
1. 基本概念
满二叉树二叉树每层节点都是满的 完全二叉树叶子节点只出现在最后一层或倒数第二层并且节点都是向左聚拢 非完全二叉树下面的二叉树不满足完全二叉树的节点都向左聚拢所以是非完全二叉树 堆也是一颗完全二叉树。 小顶堆根节点是最小值并且子节点大于等于父节点大顶堆根节点是最大值并且子节点小于等于父节点
由于树的特性堆可以用数组索引的形式表示以小顶堆为例在下面的小顶堆里依次从上到下从左往右给节点编号根节点的编号是0, 对应的数组为 对比数组和堆堆的索引有以下的性质
根节点索引是0若当前节点索引为i如果它有父节点父节点的索引是(i-1)/2C向下取整若当前节点索引为i如果它有左节点左节点的索引是2*i1如果它有右节点右节点的索引是2*i2设数组的长度为len最后一个非叶子节点的索引是(len-2)/2比如上面的K是9最后一个非叶子节点的索引是(9-2)/23
2. 堆的基本操作
C有heapn内置函数来实现具体看c重拾 STL之heap堆。这里我们讲解原理下面以小顶堆为例描述堆的相关操作
2.0 交换节点操作
我们先定义交换节点的操作为后面调整为堆做准备
void HeapSwap(vectorint minHeap, int curIndex, int swapIndex)
{int t minHeap[curIndex];minHeap[curIndex] minHeap[swapIndex];minHeap[swapIndex] t;
}2.1 下浮操作
下浮操作是通过下浮的方式把一个完全二叉树调整为堆具体的步骤是将它与它的左儿子右儿子比较大小如果不满足小顶堆的性质当前节点的值大于等于左右孩子的节点的值当前节点需要与左右孩子的最小值节点交换位置否则不满足堆的性质递归的完成这个过程。时间复杂度是log(n) 我们定义一个swapIndex记录需要交换调整的节点索引如果需要调整这个索引是当前节点和左右子节点索引的最小值这个过程要注意判断边界条件
void HeapSiftDown(vectorint minHeap, int curIndex)
{int leftChildIndex 2 * curIndex 1; // 左孩子节点的索引int rightChildIndex 2 * curIndex 2; // 右孩子节点的索引int swapIndex curIndex; // 定义调整的节点索引// 判断左右孩子是否小于当前元素如果是把swapIndex赋值为孩子索引if (leftChildIndex minHeap.size() minHeap[leftChildIndex] minHeap[swapIndex])swapIndex leftChildIndex;if (rightChildIndex minHeap.size() minHeap[rightChildIndex] minHeap[swapIndex])swapIndex rightChildIndex;// 判断交换索引和当前索引是不是一样如果不一样说明要交换然后继续SiftDown直到到最后一个节点if (curIndex ! swapIndex){HeapSwap(minHeap, curIndex, swapIndex);HeapSiftDown(minHeap, swapIndex);}
}2.2 上浮操作
上浮操作是通过上浮的方式把一个完全二叉树调整为堆具体的步骤是将它与它的父亲节点比较大小如果不满足小顶堆的性质父亲的节点的值大于等于当前节点的值当前节点与父亲节点交换位置否则不满足堆的性质递归的完成这个过程。时间复杂度是log(n) 我们类似上浮操作定义一个swapIndex记录需要交换调整的节点索引如果需要调整这个索引是父亲节点的索引这个过程要注意判断边界条件
void HeapSiftUp(vectorint minHeap, int curIndex)
{int parentIndex (curIndex - 1) / 2;//父亲节点的索引int swapIndex curIndex;// 定义调整的节点索引// 判断左右孩子是否小于当前元素如果是把swapIndex赋值为孩子索引if (parentIndex 0 minHeap[curIndex] minHeap[parentIndex])swapIndex parentIndex;// 判断交换索引和当前索引是不是一样如果不一样说明要交换然后继续SiftUp直到到最后一个节点if (curIndex ! swapIndex){HeapSwap(minHeap, curIndex, swapIndex);HeapSiftUp(minHeap, swapIndex);}
}2.3 给定一个数组建堆
建堆有上浮和下浮两种方法
如果是下浮的方法可以直接从最后一个不是叶节点的节点开始往上下浮叶子节点没有左右孩子一定不需要交换。这里使用了前面堆索引性质的第四条 设数组的长度为len最后一个非叶子节点的索引是(len-2)/2 void HeapBuild(vectorint array)
{int lastNoLeafIndex (array.size() - 2) / 2;for (int i lastNoLeafIndex; i 0; i--)//从最后一个不是叶节点的节点开始往上下浮HeapSiftDown(array, i);
}如果是上浮的方法则从索引为1节点开始往下上浮根节点没有父亲节点一定不需要交换。
void HeapBuild(vectorint array)
{for (int i 1; i array.size(); i)//从索引为1节点开始往下上浮HeapSiftUp(array, i);
}使用下浮建堆的时间复杂度是O(n)而使用上浮建堆的时间复杂度是O(nlogn)建议使用下浮建堆。关于复杂度参考How can building a heap be O(n) time complexity?
2.4 Pop操作
pop操作是把根节点弹出返回并重新调整剩余元素构成的数组为堆数组的长度为len这里我们把根节点和最后一个节点交换中间要保留根节点的值然后把数组调整为len-1因为弹出一个元素了重新用下浮调整为堆然后返回堆的根节点的值。时间复杂度是log(n)
int HeapPop(vectorint minHeap)
{int value minHeap[0];//保留堆的根节点的值int len minHeap.size();//记录堆的大小HeapSwap(minHeap, 0, len - 1);//把堆的根节点和最后一个节点交换minHeap.resize(len - 1);//调整数组长度为len-1HeapSiftDown(minHeap, 0);//下浮调整为堆return value;//返回堆的根节点的值
}2.5 Push操作
push操作是在数组末尾加入元素num然后重新调整成堆。相比pop操作push操作就简单很多了我们先在数组末尾加入元素num然后从最后一个元素的索引开始使用上浮即可。时间复杂度是log(n)
void HeapPush(vectorint minHeap, int num)
{minHeap.push_back(num);//在数组末尾加入元素numHeapSiftUp(minHeap, minHeap.size() - 1);//从最后一个元素的索引开始使用上浮
}测试
完整代码
#include iostream
#include vector
using namespace std;void HeapSiftDown(vectorint minHeap, int curIndex);
void HeapSiftUp(vectorint minHeap, int curIndex);
void HeapSwap(vectorint minHeap, int curIndex, int swapIndex);
void HeapBuild(vectorint array);
void HeapPush(vectorint minHeap, int num);void HeapBuild(vectorint array)
{int lastNoLeafIndex (array.size() - 2) / 2;for (int i lastNoLeafIndex; i 0; i--)HeapSiftDown(array, i);
}void HeapSiftDown(vectorint minHeap, int curIndex)
{int leftChildIndex 2 * curIndex 1; int rightChildIndex 2 * curIndex 2;int swapIndex curIndex; if (leftChildIndex minHeap.size() minHeap[leftChildIndex] minHeap[swapIndex])swapIndex leftChildIndex;if (rightChildIndex minHeap.size() minHeap[rightChildIndex] minHeap[swapIndex])swapIndex rightChildIndex;if (curIndex ! swapIndex){HeapSwap(minHeap, curIndex, swapIndex);HeapSiftDown(minHeap, swapIndex);}
}void HeapSiftUp(vectorint minHeap, int curIndex)
{int parentIndex (curIndex - 1) / 2;int swapIndex curIndex;if (parentIndex 0 minHeap[curIndex] minHeap[parentIndex])swapIndex parentIndex;if (curIndex ! swapIndex){HeapSwap(minHeap, curIndex, swapIndex);HeapSiftUp(minHeap, swapIndex);}
}
void HeapSwap(vectorint minHeap, int curIndex, int swapIndex)
{int t minHeap[curIndex];minHeap[curIndex] minHeap[swapIndex];minHeap[swapIndex] t;
}int HeapPop(vectorint minHeap)
{int value minHeap[0];int len minHeap.size();HeapSwap(minHeap, 0, len - 1);minHeap.resize(len - 1);HeapSiftDown(minHeap, 0);return value;
}void HeapPush(vectorint minHeap, int num)
{minHeap.push_back(num);HeapSiftUp(minHeap, minHeap.size() - 1);
}int main()
{vectorint array{9, 31, 40, 22, 10, 15, 1, 25, 91};cout The origin array is endl;for (auto t : array)cout t ;cout endl --------------------------------------------------- endl;// 建堆HeapBuild(array);cout After build the heap, the array is endl;for (auto t : array)cout t ;cout endl --------------------------------------------------- endl;// pop元素int top HeapPop(array);cout The pop value is top endl;cout After pop, the array is endl;for (auto t : array)cout t ;cout endl --------------------------------------------------- endl;// push元素HeapPush(array, 1);cout After push, the array is endl;for (auto t : array)cout t ;cout endl --------------------------------------------------- endl;
} 可以自行印证上面满足小顶堆。大顶堆的思路和小顶堆的思路差不多。读者可以自己实现一下。
3. 堆的相关使用
3.1 堆排序
堆排序基本的思路是
初始化数组建堆数组的根节点和堆的最后一个节点交换剩余元素重新排成堆堆的长度减1然后继续第2步操作直到数组的长度为1
这里也放一个算法导论的截图不过它的根节点的索引是1思路是差不多的 我们这里使用小顶堆小顶堆的根节点是最小值每次第2步和后面的节点做交换所以最后排序是从大到小最小值根节点都放到数组的后面。
前面的建堆是对整个数组来说的但是对于堆排序我们需要划定要排序数组的范围所以我们对建堆和下浮两个操作另外定义一个函数
HeapSiftDown函数
注意这里的数组越界处理改为了传入的heapLength我们只需要对0-heapLength-1范围的数组做下浮的操作
void HeapSiftDown(vectorint minHeap, int curIndex, int heapLength)
{int leftChildIndex 2 * curIndex 1; // 左孩子节点的索引int rightChildIndex 2 * curIndex 2; // 右孩子节点的索引int swapIndex curIndex; // 定义和当前索引交换的索引// 判断左右孩子是否小于当前元素如果是把swapIndex换给孩子索引注意这里的数组越界处理改为了传入的heapLength if (leftChildIndex heapLength minHeap[leftChildIndex] minHeap[swapIndex])swapIndex leftChildIndex;if (rightChildIndex heapLength minHeap[rightChildIndex] minHeap[swapIndex])swapIndex rightChildIndex;// 判断交换索引和当前索引是不是一样如果不一样说明要交换继续SiftDown直到到最后一个节点if (curIndex ! swapIndex){HeapSwap(minHeap, curIndex, swapIndex);HeapSiftDown(minHeap, swapIndex, heapLength);}
}HeapBuild函数
注意这里的计算最后一个非叶子节点的索引使用了传入的heapLength相当于对0-heapLength-1范围的数组建堆
void HeapBuild(vectorint array, int heapLength)
{int lastNoLeafIndex (heapLength - 2) / 2;//注意这里最后一个非叶子节点的索引使用的是传入的heapLengthfor (int i lastNoLeafIndex; i 0; i--)HeapSiftDown(array, i, heapLength);
}OK我们可以写堆排序了传入一个数组
void HeapSort(vectorint array)
{int heapLength array.size();//建堆的长度int len array.size();//数组的长度HeapBuild(array, heapLength);for (int i len - 1; i 1; --i)//遍历到索引1就行索引0不需要遍历因为只有一个数了{HeapSwap(array, 0, i);//把索引0根节点和索引i节点交换heapLength--;//建堆的长度减1HeapBuild(array, heapLength);//再次对0~heapLength-1的数组建堆}
}测试堆排序
#include iostream
#include vector
using namespace std;
void HeapBuild(vectorint array, int heapLength);
void HeapSort(vectorint array);void HeapBuild(vectorint array, int heapLength)
{int lastNoLeafIndex (heapLength - 2) / 2;//注意这里最后一个非叶子节点的索引使用的是传入的heapLengthfor (int i lastNoLeafIndex; i 0; i--)HeapSiftDown(array, i, heapLength);
}
void HeapSort(vectorint array)
{int heapLength array.size();//建堆的长度int len array.size();//数组的长度HeapBuild(array, heapLength);for (int i len - 1; i 1; --i)//遍历到索引1就行索引0不需要遍历因为只有一个数了{HeapSwap(array, 0, i);//把索引0根节点和索引i节点交换heapLength--;//建堆的长度减1HeapBuild(array, heapLength);//再次对0~heapLength-1的数组建堆}
}
int main()
{vectorint array{9, 31, 40, 22, 10, 15, 1, 25, 91};cout The origin array is endl;for (auto t : array)cout t ;cout endl --------------------------------------------------- endl;// sort元素HeapSort(array);cout After sort, the array is endl;for (auto t : array)cout t ;return 0;
}可以看到从大到小进行了排序如果用大顶堆就是从小到大排序。
3.2 优先队列 优先级队列虽然也叫队列但是和普通的队列还是有差别的。普通队列出队顺序只取决于入队顺序而优先级队列的出队顺序总是按照元素自身的优先级。可以理解为优先级队列是一个排序后的队列。 堆和优先级队列非常相似一个堆就可以看作一个优先级队列。往优先级队列中插入一个元素就相当于往堆中插入一个元素从优先级队列中取出优先级最高的元素就相当于取出堆顶元素大顶堆–最大值小顶堆–最小值。不过优先级我们还可以自己额外定义。C有priority_queue来实现具体可以看c优先队列(priority_queue)用法详解。
所以优先队列有两个操作分别是pop弹出和push加入pop即弹出根节点push即把新的元素加入优先队列两种操作过后要保证剩余的元素构成的还是一个堆。直接使用前面所说的pop和push操作即可。
4. 典型例题
347. 前 K 个高频元素 前K个元素先用哈希表记录元素的频率然后可以使用小根堆如果队列元素超过K可以弹出根节点最小的元素遍历完以后队列里剩下的就是前K大的元素。
class Solution {
public:static bool cmp(pairint, int a, pairint, int b){return a.second b.second;}vectorint topKFrequent(vectorint nums, int k) {vectorint ans;unordered_mapint, int mp;for (auto t: nums)mp[t];priority_queuepairint, int, vectorpairint, int, decltype(cmp) que(cmp);for (auto it mp.begin(); it ! mp.end(); it){que.push(*it);if (que.size() k)que.pop();}while (!que.empty()){ans.push_back(que.top().first);que.pop();}return ans;}
};关于priority_queue的比较函数cmp也可以使用仿函数
class Solution {
public:class cmp {public:bool operator() (const pairint, int lhs, const pairint, int rhs) {return lhs.second rhs.second;}};vectorint topKFrequent(vectorint nums, int k) {vectorint ans;unordered_mapint, int mp;for (auto t: nums)mp[t];priority_queuepairint, int, vectorpairint, int, cmp que;for (auto it mp.begin(); it ! mp.end(); it){que.push(*it);if (que.size() k)que.pop();}while (!que.empty()){ans.push_back(que.top().first);que.pop();}return ans;}
};内置类型比如int的话cmp可以直接使用greaterint小根堆和lessint大根堆如果比较自定义的Node类型可以在Node里重载
#include queue
#include iostream
using namespace std;
struct Node
{int x, y;bool operator(const Node rhs) const{return this-x rhs.x; // 用x比较这里是是小根堆}
};
int main()
{priority_queueNode que;que.push(Node{1, 2});que.push(Node{2, 1});que.push(Node{4, 2});while (!que.empty()){cout que.top().x que.top().y endl;que.pop();}
}215. 数组中的第K个最大元素
和上题类似我们使用一个小顶堆遍历完整个数组最后剩下的根节点就是第K大元素了。
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint, vectorint, greaterint que;for (auto t:nums){que.push(t);if (que.size() k){que.pop();}}return que.top();}
};295. 数据流的中位数
维护一个大根堆和一个小根堆大根堆queMin记录小于等于中位数的那些数小根堆queMax记录大于中位数的那些数。
大根堆queMin: 大-小 小根堆queMax小-大
findMedian小根堆的元素个数比大根堆的元素的个数大1或两者相等如果是奇数直接取小根堆的根节点元素如果是偶数取两个堆的根节点的平均值注意返回是double所以除以2不行要除以2.0
addNum由于小根堆的元素个数比大根堆元素个数大1或两者相等所以我们优先处理小根堆
如果queMax的维度和queMin的维度是一样的那么先往queMax里push num然后queMin添加queMax的堆顶元素queMax弹出元素。如果queMax的维度比queMin的维度小这时候是小1那么先往queMin里push num然后queMax添加queMin的堆顶元素queMin弹出元素。
class MedianFinder {
public:MedianFinder() {}void addNum(int num) {if (queMin.size() queMax.size()){queMax.push(num);queMin.push(queMax.top());queMax.pop();}else{queMin.push(num);queMax.push(queMin.top());queMin.pop();}}double findMedian() {if (queMin.size() queMax.size())return queMin.top();return (queMin.top() queMax.top()) / 2.0;}
private:priority_queueint, vectorint, lessint queMin;priority_queueint, vectorint, greaterint queMax;};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj new MedianFinder();* obj-addNum(num);* double param_2 obj-findMedian();*/
