优先队列 – 数据结构 （二叉堆）
最后更新于：2022-04-01 20:06:08
优先队列包括二叉堆、d-堆、左式堆、斜堆、二项队列等
1、二叉堆
堆是一棵被完全填满的二叉树，有可能例外的是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。
堆序的性质：在一个堆中，对于每一个节点X，X的父亲的关键字小于（或等于）X中的关键字，根节点除外（它没有父节点）。完全二叉树可以用数组实现。
//关于二叉堆的头文件定义
如果要插入的元素是新的最小值，那么它将一直被推向堆顶。这样在某一个时刻，i将是1，我们就需要另Insert函数令程序跳出while循环，这个值必须保证小于或者至少等
于堆中的任何值，我们称之为标记。
~~~
#ifndef BITHEAP_H_INCLUDED
#define BITHEAP_H_INCLUDED
#include
#include
typedef int ElementType;
struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;
PriorityQueue BitHeap_Init(int max_elements);
void BitHeap_Insert(ElementType x, PriorityQueue H);
ElementType BitHeap_Delete(PriorityQueue H);
void BitHeap_Show(PriorityQueue H);
int BitHeap_Free(PriorityQueue H);
#endif // BITHEAP_H_INCLUDED
~~~
//二叉堆中的功能函数的定义
~~~
#include "bitheap.h"
struct HeapStruct
{
int Capacity;
int Size;
ElementType *Elements;
};
static void print_err(char *str);
static int IsFull(PriorityQueue H);
static int IsEmpty(PriorityQueue H);
PriorityQueue BitHeap_Init(int max_elements)
{
PriorityQueue H;
H = (PriorityQueue)malloc(sizeof(struct HeapStruct));
if(H == NULL)
print_err("no space for H in BitHeap");
H->Elements = (ElementType *)malloc((max_elements+1) * sizeof(ElementType));
H->Elements[0] = (1<<31);
if(H->Elements == NULL)
print_err("no space for H->Elements in BitHeap");
H->Capacity = max_elements;
H->Size = 0;
return H;
}
void BitHeap_Insert(ElementType x, PriorityQueue H)
{
int i;
if(IsFull(H))
{
printf("the heap is full\n");
return;
}
for(i = ++H->Size; H->Elements[i/2] > x; i /= 2)
H->Elements[i] = H->Elements[i/2];
H->Elements[i] = x;
}
ElementType BitHeap_Delete(PriorityQueue H)
{
ElementType min_val, last_val;
int i, child;
if(IsEmpty(H))
{
printf("the bitheap is empty\n");
return (1<<31);
}
min_val = H->Elements[1];
last_val = H->Elements[H->Size--];
for(i = 1; 2*i < H->Size; i = child)
{
child = 2 * i;
if(child != H->Size && (H->Elements[child+1] < H->Elements[child]))
child++;
if(last_val > H->Elements[child])
H->Elements[i] = H->Elements[child];
else
break;
}
H->Elements[i] = last_val;
return min_val;
}
void BitHeap_Show(PriorityQueue H)
{
int i;
if(H != NULL)
{
for(i = 1; i <= H->Size; i++)
printf("%d ", H->Elements[i]);
}
printf("\n");
}
int BitHeap_Free(PriorityQueue H)
{
if(H != NULL)
{
free(H->Elements);
free(H);
}
return 1;
}
/*
* flowing function is used by function in bitheap.c
*/
static int IsFull(PriorityQueue H)
{
return (H->Size == H->Capacity);
}
static int IsEmpty(PriorityQueue H)
{
return (H->Size == 0);
}
static void print_err(char *str)
{
perror(str);
exit(-1);
}
~~~
//关于二叉堆的测试函数 main.c
~~~
#include
#include
#include "bitheap.h"
int main()
{
PriorityQueue H;
H = BitHeap_Init(15);
BitHeap_Insert(4, H);
BitHeap_Insert(2, H);
BitHeap_Insert(7, H);
BitHeap_Insert(3, H);
BitHeap_Insert(12, H);
BitHeap_Insert(8, H);
BitHeap_Show(H);
BitHeap_Delete(H);
BitHeap_Show(H);
if(BitHeap_Free(H))
printf("\nfree the bitheap is ok.\n");
return 0;
}
~~~
2、d-堆是二叉堆的简单推广，它恰像一个二叉堆，只是所有的节点都有d个儿子（可以说二叉堆是2-堆）
3、优先队列还包括了左式堆、斜堆、二项队列等。
可以参考《数据结构与算法分析-C语言描述》第6章 - 优先队列（堆）
';