堆的构建 (一)

堆，又可以称为优先级队列，这种数据结构插入和删除操作需要o(lgn)的时间复杂度，但是却能在o(1)的时间复杂度内取出最大值或最小值。

堆有最大堆和最小堆，最大堆中任意节点的关键码大于或等于它的左、右子女的关键码，相反，最小堆中任意节点的关键码小于或等于它的左、右子女的关键码。

如果堆的索引从0开始，则有如下关系式：

(1)左子女：2*i+1

(2)右子女：2*i+2

(3)父亲节点：向下取整((i-1)/2)

注：这是索引，给定一个数组长度，应该先通过len-1得到最后一个元素的索引，在通过第三条的公式开始调整。

堆的调整

（1）向下调整（删除堆顶元素）

/*copyright@ CNV && lsj*/
/*最小堆*/

#include
#include
using namespace std;

#define LEFT(i) (((i)<<1)+1)
#define RIGHT(i) (((i)<<1)+2)
#define CHILD(i) (((i)-1)>>1)
typedef int RecType;

/*从上往下调整 ---删除堆顶元素的调整*/
void SiftDown(RecType minHeap[],int low,int high)
{
int i = low;
int j = LEFT(i);
int base = minHeap[i];
while(j<=high){
//与小的比较,必须是j if(j if(base<=minHeap[j])break;
else{
//上移
minHeap[i] = minHeap[j];
i = j;
j = LEFT(i);
}
}
minHeap[i] = base;
};

/*copyright@ CNV && lsj*/
/*最小堆*/

#include
#include
using namespace std;

#define LEFT(i) (((i)<<1)+1)
#define RIGHT(i) (((i)<<1)+2)
#define CHILD(i) (((i)-1)>>1)
typedef int RecType;

/*从上往下调整 ---删除堆顶元素的调整*/
void SiftDown(RecType minHeap[],int low,int high)
{
int i = low;
int j = LEFT(i);
int base = minHeap[i];
while(j<=high){
//与小的比较,必须是j if(j if(base<=minHeap[j])break;
else{
//上移
minHeap[i] = minHeap[j];
i = j;
j = LEFT(i);
}
}
minHeap[i] = base;
};

（2）向上调整（插入元素，插入堆尾部）

[cpp
/*从下往上调整 ---往堆中插入元素的调整*/
void SiftUp(RecType minHeap[],int high)
{
int j = high;
int i = CHILD(j);
int base = minHeap[j];
while(i>0){
if(minHeap[i]<=base)break;
else{
//下移
minHeap[j] = minHeap[i];
j = i;
i = CHILD(j);
}
}
minHeap[j] = base;
};

/*从下往上调整 ---往堆中插入元素的调整*/
void SiftUp(RecType minHeap[],int high)
{
int j = high;
int i = CHILD(j);
int base = minHeap[j];
while(i>0){
if(minHeap[i]<=base)break;
else{
//下移
minHeap[j] = minHeap[i];
j = i;
i = CHILD(j);
}
}
minHeap[j] = base;
};

（3）堆排序

[cpp]
//逆序--》从大到小
void HeapSort(RecType arr[],int len)
{
int lastIndex = len -1;//由长度转换为索引
int beginIndex = (lastIndex-1)>>1;
//下面构建了一个堆,o(nlogn)
while(beginIndex>=0){
SiftDown(arr,beginIndex,len-1);
--beginIndex;
}

//排序
for(int i=len-1;i>=0;i--){
swap(arr[0],arr[i]);
SiftDown(arr,0,i-1);
}
};

//逆序--》从大到小
void HeapSort(RecType arr[],int len)
{
int lastIndex = len -1;//由长度转换为索引
int beginIndex = (lastIndex-1)>>1;
//下面构建了一个堆,o(nlogn)
while(beginIndex>=0){
SiftDown(arr,beginIndex,len-1);
--beginIndex;
}

//排序
for(int i=len-1;i>=0;i--){
swap(arr[0],arr[i]);
SiftDown(arr,0,i-1);
}
};

STL中的堆（面试的时候用得着）

（1）利用make_heap构建堆（STL源码剖析P181）

STL提供堆结构，但却是幕后工作者，heap可以分为max_heap和min_heap。记住几个重要的接口：make_heap、push_heap、pop_heap、sort_heap。

这几个接口输入参数是这样的：

template

inline void make_heap(RandomAccessIterator first,RandomAccessIterator last, Compare comp);

注：通过给上面各函数传入不同的仿函数，分别构造最大堆还是最小堆

[cpp]
#include
#include
#include
#include
using namespace std;
int main()
{
int arr[]={0,1,2,3,4,8,9,3,5};
vectorivec(arr,arr+9);
//greater comp;//最小堆
less comp;//最