堆
- 实现一个小顶堆、大顶堆、优先级队列
- 实现堆排序
- 利用优先级队列合并K个有序数组
- 求一组动态数据集合的最大Top K
优先级队列是用来维护一组元素构成的集合S 的数据结构，每一个元素都含有一个关键字key。一个最大优先级队列支持一下操作：
Insert(S,x)：把元素x插入到队列中，与一般队列不同的是，优先级队列入队的操作总和队列中已有的元素进行比较，找到适当的位置进行插入，本例中，入队的操作总是能使优先级队列保持有序状态。
Maximum(S)：返回S中具有最大关键字的元素
Extract_Max(S)：去掉并返回S中具有最大关键字的元素，其实就是出队操作，在大顶堆中，由于最大元素总是在根节点处，所以出队时仅需要去掉根节点并重新建堆即可。
Increase_Key(S,x,k)：将元素x的值增加到k，这里k的值不能小于x的值
#include <stdio.h>
#include <stdlib.h>
#define INF -10000//为什么要设置为那么小？相当于把这个元素放在队尾，增加到key时一层一层向上，完成队列的入队操作
#define MAX 20
/*一下操作是大顶堆的基本操作*/
//堆的大小，注意，和数组本身的大小事有区别的，在堆排序的函数中要尤其小心
int Heap_Size=20;
//保持堆的性质，其实就是拿A[i]和左右两个孩子比较大小，然后递归下去就行了
void MAX_HEAPIFY(int* A,int i)
{
int Largest;
int L=2*i;
int R=2*i+1;
if(L<=Heap_Size&&A[L]>A[i])
Largest=L;
else
Largest=i;
if(R<=Heap_Size&&A[R]>A[Largest])
Largest=R;
if(Largest!=i)
{
int temp=A[i];
A[i]=A[Largest];
A[Largest]=temp;
MAX_HEAPIFY(A,Largest);
}
}
//建堆的过程
void Build_Max_Heap(int* A)
{
int i=MAX/2;
for(;i>=1;i--)
{
MAX_HEAPIFY(A,i);
}
}
//堆排序算法的过程
void Heap_Sort(int* A)
{
Build_Max_Heap(A);
int i=MAX;
for(;i>2;i--)
{
printf("%d ",A[1]);
int temp=A[1];
A[1]=A[i];
A[i]=temp;
Heap_Size--;
MAX_HEAPIFY(A,1);
}
}
/*以下代码是优先级队列的基本操作*/
//返回最大值
int Heap_Maximum(int* A)
{
return A[1];
}
//出队操作，也就是讲A[1]出队，并重新生成大顶堆
int Heap_Extract_Max(int* A)
{
if(Heap_Size<1)
exit(-1);
int max=A[1];
A[1]=A[Heap_Size];
Heap_Size--;
MAX_HEAPIFY(A,1);
return max;
}
//将其中一个元素的值增大到key后堆的变化，主要为后续的入队操作打下基础
void Heap_Incerase_Key(int* A,int i,int key)
{
if(key<A[i])
exit(-1);
A[i]=key;
while(i>1&&A[i/2]<A[i])
{
int temp=A[i/2];
A[i/2]=A[i];
A[i]=temp;
i=i/2;
}
}
//入队操作，在数组左后一个位置放上值为非常小的数，然后通过Heap_Incerase_Key重新构造堆的结构
void Max_Heap_Insert(int* A,int key)
{
Heap_Size++;
A[Heap_Size]=INF;
Heap_Incerase_Key(A,Heap_Size,key);
}
//主函数进行测试，注意，数组下标从1开始，第一个元素存放数组的大小
int main(void)
{
int A[MAX+1]={MAX,34,23,67,34,2,5,6,1,78,34,2,4,5,44,12,6,97,23,54,10};
Build_Max_Heap(A);
printf("出队的元素是%d
",Heap_Extract_Max(A));
printf("出队的元素是%d
",Heap_Extract_Max(A));
Max_Heap_Insert(A,100);
printf("出队的元素是%d
",Heap_Extract_Max(A));
return 0;
}
#include <iostream>
#include <stdlib.h>
using namespace std;
//堆调整
//将nums[s..m]调整为大顶堆，其中除了nums[s]之外均满足大顶堆的定义
void HeapAdjust(int nums[],int s, int m)
{
int j;
nums[0] = nums[s]; //nums之后跟新为该节点作为根节点的所有子孙的关键字最大值
for(j = 2 * s;j <= m;j *=2 ) //沿着关键字较小的孩子向下筛选
{
if(j < m && nums[j] < nums[j + 1])
j++; //j为关键字中较大的记录的下标
if(nums[0] >= nums[j])
break; //满足大顶堆条件，直接跳出
nums[s] = nums[j];
s = j;
}
nums[s] = nums[0];
}
void HeapSort(int nums[],int n)
{
//调整为大顶堆
for(int i = n/2; i > 0; i--)
{
HeapAdjust(nums, i, n);
}
//将整个根节点根节点最后一个子节点进行交换
for(int i = n; i > 1; i--)
{
swap(nums[1],nums[i]);
HeapAdjust(nums, 1, i -1);
}
}
int main()
{
int nums[10] = {-1,1,2,5,3,6,4,9,7,8};
HeapSort(nums,9);
cout<< "排序结果:";
for(int i = 1; i < 10;i++)
{
cout<< nums[i]<< " ";
}
system("pause");
return 0;
}
#include <iostream>
#include <stdlib.h>
using namespace std;
//堆调整
//将nums[s..m]调整为小顶堆，其中除了nums[s]之外均满足小顶堆的定义
void HeapAdjust(int nums[],int s, int m)
{
int j;
nums[0] = nums[s]; //nums之后跟新为该节点作为根节点的所有子孙的关键字最小值
for(j = 2 * s;j <= m;j *=2 ) //沿着关键字较小的孩子向下筛选
{
if(j < m && nums[j] < nums[j + 1])
j++; //j为关键字中较小的记录的下标
if(nums[0] >= nums[j])
break; //满足小顶堆条件，直接跳出
nums[s] = nums[j];
s = j;
}
nums[s] = nums[0];
}
void HeapSort(int nums[],int n)
{
//调整为小顶堆
for(int i = n/2; i > 0; i--)
{
HeapAdjust(nums, i, n);
}
//将整个根节点根节点最后一个子节点进行交换
for(int i = n; i > 1; i--)
{
swap(nums[1],nums[i]);
HeapAdjust(nums, 1, i -1);
}
}
int main()
{
int nums[10] = {-1,1,2,5,3,6,4,9,7,8};
HeapSort(nums,9);
cout<< "排序结果:";
for(int i = 1; i < 10;i++)
{
cout<< nums[i]<< " ";
}
system("pause");
return 0;
}