優先隊列包括二叉堆、d-堆、左式堆、斜堆、二項隊列等
1、二叉堆
?????? 堆是一棵被完全填滿的二叉樹，有可能例外的是在底層，底層上的元素從左到右填入。這樣的樹稱為完全二叉樹。
?????? 堆序的性質：在一個堆中，對于每一個節點X，X的父親的關鍵字小于（或等于）X中的關鍵字，根節點除外（它沒有父節點）。完全二叉樹可以用數組實現。
//關于二叉堆的頭文件定義
? ? ??如果要插入的元素是新的最小值，那么它將一直被推向堆頂。這樣在某一個時刻，i將是1，我們就需要另Insert函數令程序跳出while循環，這個值必須保證小于或者至少等
于堆中的任何值，我們稱之為標記。
~~~
#ifndef BITHEAP_H_INCLUDED
#define BITHEAP_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
#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章 - 優先隊列（堆）
