优先队列(Priority Queue): 特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。
若采用数组或链表实现优先队列
数组:
插入一元素总是插入尾部 ~Θ(1)
删除一查找最大(或最小)关键字 ~Θ(n)
从数组中删去需要移动元素 ~O(n)
链表:
插入一元素总是插入链表的头部 ~Θ(1)
删除一查找最大(或最小)关键字 ~Θ(n)
删去结点 ~Θ(1)
有序数组:
插入 - 找到合适的位置 ~ O(n)或O(log2N)
移动元素并插入 ~O(n)
删除 - 删去最后一个元素 ~Θ(1)
有序链表:
插入- 找到合适的位置 ~O(n)
插入元素 ~Θ(1)
删除- 删除首元素或最后元素 ~Θ(1)
- 我们用优先队列的完全二叉树表示
堆的两个特性：
- 结构性：用数组表示的完全二叉树；
- 有序性：任意结点的关键字是其子树所有节点的最大值（或最小值）
“最大堆(MaxHeap)”,也称“大顶堆”：最大值
“最小堆(MinHeap)”,也称“小顶堆”：最小值
最大堆：
最小堆：
typedef int ElementType;
typedef struct HeapStruct{
ElementType *elements;
int size; //堆的当前元素个数
int capacity; //堆的最大容量
} *MaxHeap;
#define MaxData 10000
//创建最大堆
MaxHeap create(int MaxSize)
{ //创建容量为MaxSize的空间的最大堆
MaxHeap h = malloc(sizeof(struct HeapStruct));
h->elements = malloc((MaxSize + 1)*sizeof(ElementType));
h->size = 0;
h->capacity = MaxSize;
//定义“哨兵”为大于堆中所有可能元素的值，以便于以后更快操作
h->elements[0] = MaxData;
return h;
}
//判断堆满
bool isFull(MaxHeap h)
{
return h->size == h->capacity;
}
//判空
bool isEmpty(MaxHeap h)
{
return h->size == 0;
}
最大堆插入
//往堆里插入元素 T=O(logN)
void insert(MaxHeap h, ElementType item)
{
int i;
if(isFull(h))
{
printf("最大堆已满");
return;
}
i = ++h->size; //i指向插入后堆中最后一个元素的位置
for (; h->elements[i/2] < item; i/=2) {
h->elements[i] = h->elements[i/2];
}
h->elements[i] = item;
}
以上可见插入操作时间复杂度为T = O(logN)
最大堆删除
//删除最大值
ElementType deleteMax(MaxHeap h)
{
if(isEmpty(h)){
printf("最大堆已为空");
return -1;
}
ElementType maxItem = h->elements[1];
ElementType item = h->elements[h->size--];
int parent = 1, child;
for (; 2*parent <= h->size; parent = child) {
child = 2*parent ;
if(child != h->size && h->elements[child + 1] > h->elements[child])
child++; //child指向左右子结点较大者
if(h->elements[child] <= item)
break;
else{
h->elements[parent] = h->elements[child];
}
}
h->elements[parent] = item;
return maxItem;
}
以上可见删除操作时间复杂度为T = O(logN)
最大堆的构建
如果我们用最大堆插入的方式构建最大堆，其时间复杂度为T = O(NlogN)。
我们可以先将数据输入到数组，然后再调整。其时间复杂度为T = O(N/2logN)。
void MaxHeapAdjust(MaxHeap h, int p);
//构建堆
MaxHeap buildMaxHeap()
{
MaxHeap h = create(10);
int arr[] = {49,38,65,97,76,13,34,27,49,11};
for (int i = 1; i <= h->capacity; i++) {
h->elements[i] = arr[i - 1];
h->size++;
}
/**
调整堆
思路跟删除堆相同
从 h->size/2 的位置往前依次调整堆
*/
for(int i = h->size/2; i > 0; i--)
{
MaxHeapAdjust(h, i);
}
return h;
}
//调整堆
void MaxHeapAdjust(MaxHeap h, int p)
{
int parent = p, child;
int item = h->elements[p];
for (; parent * 2 <= h->size; parent = child) {
child = 2 * parent;
if(child != h->size && h->elements[child + 1] > h->elements[child])
child++;
if(item >= h->elements[child])
break;
else
h->elements[parent] = h->elements[child];
}
h->elements[parent] = item;
}
最大堆堆排序
我们直接调用删除堆，返回最大值的方式，就可以获取从大到小的排序。
//堆排序
void MaxHeapSort(MaxHeap h)
{
printf("堆排序：");
for (int i = 1; i <= h->capacity; i++) {
ElementType item = deleteMax(h);
printf("%d ",item);
}
}
调用堆排序
MaxHeap h = buildMaxHeap();
MaxHeapSort(h);
执行结果：堆排序：97 76 65 49 49 38 34 27 13 11
