首页 > 代码库 > 堆--LogN的数据结构
堆--LogN的数据结构
我们这里的堆是指用来表示元素集合的一种数据结构
一个二叉树是一个堆是由堆的两个性质决定的（以小根堆为例）
1：任何节点的值都小于或等于其子节点的值
2：该二叉树最多在两层上具有叶节点，其中最底层的叶节点尽可能的靠左分布
我们可以从数学上约束这两个性质
x[i/2]<=x[i](2<=i<=n)
从这个性质我们可以定义heap(l,u):x[i/2]<=x[i](2l<=i<=u)
下面我们考虑两种情况：
1：当x[1,...n-1]是堆时，在x[n]中放置一个任何的元素可能无法产生heap(1,n)
2：当x[1...n]是一个堆时，给x[1]分配一个新值得到heap(2,n)，如何得到heap(1,n)
现在我们来探讨这两个问题：
x[n]即为图中带圈的元素，该元素一直往上与父节点交换，知道该节点的值大于等于其父节点（或者位于树根）为止
如果过程中heap(1,n-1)为真，那么heap(1,n)为真
void siftup(int n)//sift 筛选{ int i=n; while(true) { if(i==1) break; int p=i/2; if(x[p]<=x[i]) break; swap(i,p); i=p; }}
x[1]即为图中带圈的元素，x[1]向下筛选，直到它没有子节点或者小于等于它的子节点
void siftdown(int n){ int i=1; while(true) { int c=2*i; if(c>n) break;//no child node if(c+1<=n)//c+1 is the right child,c+1<=n,i has right child if(x[c+1]<x[c]) c++;//select lesser one //c is the lesser child if(x[i]<=x[c]) break; swap(c,p); i=c; }}
通过解决这两个问题，我们实现了给堆增加一个元素或者删除最小的元素（最小堆）
现在我们考虑用堆的这两个操作来实现另一个数据结构--优先级队列
优先级队列（priority queue） 是0个或多个元素的集合，每个元素都有一个优先权，对优先级队列执行的操作有（1）查找（2）插入一个新元素 （3）删除
一般情况下，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素 。对于优先权相同的元素，可按先进先出次序处理或按任意优先权进行。
如果用我们上面讨论的最小堆来实现的话，那么对应的操作如下：
查找：返回x[1]
插入：插入新元素是将n+1，然后将新元素放在x[n]处，这样我们就具备了调用siftup的前提：heap(1,n-1)
删除：由于是最小堆，x[1]即为优先权最高的元素，删除x[1]，我们可以将x[n]移动到x[1]并将n-1，这样集合中的元素都在x[1..n]中了，并且heap(2,n)为真，那我们就可以调用siftdown了
template<class T>class priqueue{private: int n,maxsize; T *x; void swap(int i,int j){ T t = x[i];x[i]=x[j];x[j]=t;}public: priqueue(int m) { maxsize=m; x= new int[maxsize+1]; n=0; } void insert(T t) { int i,p; x[++n]=t; for(i=n;i>1 && x[p=i/2]>x[i];i=p) swap(i,p); } T extractmin() { int i,c; T t = x[1]; x[1]=x[n--]; for(i=1;(c=2*i)<=n;i=c) { if(c+1<=n&&x[c+1]<x[c]) c++; if(x[i]<=x[c]) break; swap(i,c); } return t; } ~priqueue(); };
优先级队列的实现为我们提供了一种简单的向量排序算法：首先在优先级队列中依次插入每个元素，然后排序删除它们
然而这种想法需要额外的一个数组的内存，但我们分析可知，是可以在一个数组上操作的，想法如下：
第一阶段：在原数组上建立堆，
第二阶段：使用堆来建立有序序列，由于x[1]是最小的元素，交换x[1]和x[n--]，然后把新的顶部元素向下筛选来重新获得堆性质，循环。
不过这样得到的是一个降序的有序序列，如果要得到升序的有序序列，我们要使用最大堆而不是最小堆
下面是实现的最小堆排序的代码：
#include <iostream>#include "stdlib.h"#include "time.h"using namespace std;int x[101]= {0};int co=0;void swap(int f,int s){ int temp=x[f];x[f]=x[s];x[s]=temp; co++;}void siftup(int n)//sift 筛选{ int i=n; while(true) { if(i==1) break; int p=i/2; if(x[p]<=x[i]) break; swap(i,p); i=p; }}void siftdown(int n){ int i=1; while(true) { int c=2*i; if(c>n) break;//no child node if(c+1<=n)//c+1 is the right child,c+1<=n,i has right child if(x[c+1]<x[c]) c++;//select lesser one //c is the lesser child if(x[i]<=x[c]) break; swap(c,i); i=c; }}int main(int argc, char const *argv[]){ srand(unsigned(time(NULL))); for(int i=1;i<101;i++) { x[i]=rand()%100; cout<<x[i]<<" "; } cout<<endl; //sort for(int i=2;i<=100;i++) siftup(i); for(int i=100;i>=2;i--) { swap(i,1); siftdown(i-1); } for(int i=1;i<101;i++) { cout<<x[i]<<" "; } cout<<endl<<co; return 0;}
堆--LogN的数据结构