優(yōu)先隊列（Priority Queue）：特殊隊列厨诸，取出元素的順序是依照元素的優(yōu)先權(quán)（關鍵字）大小，而不是元素進入隊列的先后順序妓布。
堆的特性
【1】結(jié)構(gòu)性：用數(shù)組表示的完全二叉樹
【2】有序性：任一節(jié)點的關鍵字是其子樹所有節(jié)點的最大值（或者最小值）
最大堆（MaxHeap）：最大值
最小堆（MinHeap）：最小值
【3】從根節(jié)點到任意節(jié)點路徑上節(jié)點序列的有序性
【堆建立】
最大堆的建立 ：時間復雜性O(n) 樹中各節(jié)點的高度和
將已經(jīng)存在的N個元素按最大堆的要求存放在一個一維數(shù)組中
從倒數(shù)第一個有兒子的節(jié)點開始酌伊，將其調(diào)整成堆
然后從右向左，從下往上依次調(diào)整成堆
每當右父節(jié)點落下時浴鸿，再調(diào)整成新的堆

/* 
  最大堆操作集
  堆是一種用數(shù)組表示的完全二叉樹
  樹:
  a
  bc
  defg
  hi######
  堆：#abcdefghi##,數(shù)組0為空
  若一個節(jié)點式i，則左兒子是2*i弦追，右兒子是2*i+1
 */

#include<stdio.h>
#include<stdlib.h>

#define MaxData 1000
//#define MaxSize 10
typedef int ElementType;
struct HeapStruct{
    ElementType *Elements; //指向數(shù)組空間的指針（存儲堆元素的一維數(shù)組）
    int Size; //當前數(shù)組長度
    int Capacity;//初始化時所定義的數(shù)組長度
};
typedef struct HeapStruct *MaxHeap;

MaxHeap CreateHeap(MaxHeap H,int MaxSize); //創(chuàng)建堆
void Insert(MaxHeap H,ElementType item); //插入元素item
ElementType DeleteMax(MaxHeap H); //取出二叉樹根節(jié)點岳链，同時刪除一個節(jié)點
int IsFull(MaxHeap H, int MaxSize);//判斷堆為空
int IsEmpty(MaxHeap H);//判斷堆為滿

int main()
{
  int MaxSize=10;
    int arrary[] = {58,25,44,18,10,26,20,12,8};
    MaxHeap heap=NULL;
    heap=CreateHeap(heap,MaxSize);
  for(int i=0;i<10;i++){
    Insert(heap,arrary[i]);
  }

  while(!IsEmpty(heap)){
    printf("%d, ", DeleteMax(heap));
  }
  putchar('\n');
  printf("%d\n",heap->Elements[0]);
    system("pause");
    return 0;
}

MaxHeap CreateHeap(MaxHeap H,int MaxSize)
{
    H=(MaxHeap)malloc(sizeof(struct HeapStruct));
    /*
    這一塊卡了好久、關于內(nèi)存那里搞錯了
    int *p;
    p=(int *)malloc(sizeof(int));
    p=NULL;
  */
    H->Elements=(ElementType *)malloc((MaxSize+1)*sizeof(ElementType));
    H->Size=0;
    H->Capacity=MaxSize;
  //最大值用作哨兵劲件，以便于以后更快操作
    H->Elements[0]=MaxData;

  return H;
}

int IsFull(MaxHeap H,int MaxSize)
{
    if(H->Size== MaxSize) return 1;
  else  return 0;
}

int IsEmpty(MaxHeap H)
{
  if(H->Size==0)  return 1;
  else return 0;
}

/* 將新增節(jié)點插入到其從父節(jié)點到根節(jié)點的有序序列中 */
void Insert(MaxHeap H,ElementType item)
{
  /* 將元素item插入最大堆H掸哑，其中H->Elements[0] */
    int i;
    if(IsFull(H, 10)){
        printf("the head is full\n");
    }else{
    i = ++H->Size; //i指向插入后堆中的最后一個元素的位置,其父節(jié)點是H->Elements[i/2]
    //過濾插入
    for( ;H->Elements[i/2]<item;i/=2)//與父節(jié)點做比較，滿足插入的有序性
      //哨兵為最大值零远，在[0]位置苗分，在比較過程中，比哨兵小牵辣，則自然落在了根節(jié)點的位置
       H->Elements[i]=H->Elements[i/2];
    H->Elements[i]=item;
  }
}

/* 
   最大堆的刪除：（根節(jié)點是最大值）
   取出根節(jié)點（最大值）元素摔癣，同時刪除堆的一個節(jié)點 
   先用最后一個元素替換根節(jié)點，
   然后再比較較大的孩子，節(jié)點下沉择浊，保證有序性
*/
ElementType DeleteMax(MaxHeap H)
{
    int parent,child;
    ElementType MaxItem,temp;
    if(IsEmpty(H)){
        printf("the MaxHeap is empty\n");
        return NULL;
    }
    MaxItem=H->Elements[1]; //保存要刪除的元素戴卜，即堆的最大值
    temp=H->Elements[H->Size--]; //用最大堆中最后一個元素從節(jié)點開始向上過濾下層節(jié)點
    /* 
       parent*2<=H->Size 判別是否有左孩子 
       從左右兒子中找到一個大的值與節(jié)點比較
       將child變量指向左右兒子中較大的的一個
    */
    for(parent=1;parent*2<=H->Size;parent=child){
        child=parent*2; //child 指向左兒子；child+1 指向右兒子
        if((child!=H->Size)&&(H->Elements[child]<H->Elements[child+1]))
            child++;
        if(temp>=H->Elements[child]) break;
        else
            H->Elements[parent]=H->Elements[child]; //較大值上浮
    }
    H->Elements[parent]=temp;
    return MaxItem;
}

最小堆操作集

/* 最小堆操作集 */

#include<stdio.h>
#include <stdlib.h>

#define MinData -1
#define MaxSize 101
typedef int ElemnetType;
typedef struct HeapStruct{
    ElemnetType *Elements;
    int Size;
    int Capacity;
}*MinHeap;

MinHeap CreateHeap(MinHeap H);
void Inster(MinHeap H,ElemnetType item);
int IsFull(MinHeap H);
int IsEmpty(MinHeap H);
ElemnetType DeleteMin(MinHeap H);

int main()
{
    int arr[]={23,26,46,24,10};
    MinHeap heap=NULL;

    heap=CreateHeap(heap);
    for(int i=0;i<5;i++){
        Inster(heap,arr[i]);
    }

    while(!IsEmpty(heap)){
        printf("%d, ", DeleteMin(heap));
    }
    putchar('\n');

    system("pause");
    return 0;
}

MinHeap CreateHeap(MinHeap H)
{
    H=(MinHeap)malloc(sizeof(struct HeapStruct));
    H->Elements=(ElemnetType *)malloc(sizeof(ElemnetType));
    H->Size=0;
    H->Capacity=MaxSize;
    H->Elements[0]= MinData;

    return H;
}

int IsFull(MinHeap H)
{
    if(H->Size==MaxSize)    return 1;
    else return 0;      
}

int IsEmpty(MinHeap H)
{
    if(H->Size==0)  return 1;
    else return 0;
}

void Inster(MinHeap H,ElemnetType item)
{
    int i;
    if(IsFull(H)){
        printf("Full\n");
    }else{
        i=++H->Size;
        for( ;item<H->Elements[i/2];i/=2)
            H->Elements[i]=H->Elements[i/2];
        H->Elements[i]=item;
    }
}

ElemnetType DeleteMin(MinHeap H)
{
    int parent,child;
    ElemnetType MinItem,temp;
    if(IsEmpty(H)){
        printf("Empty\n");
        return NULL;
    }
    MinItem=H->Elements[1];
    temp=H->Elements[H->Size--];
    for(parent=1;parent*2<H->Size;parent=child){
        child=parent*2;
        if((child!=H->Size)&&(H->Elements[child]>H->Elements[child+1]))
            child++;
        if(temp<H->Elements[child]) break;
        else
            H->Elements[parent]=H->Elements[child];
    }
    H->Elements[parent]=temp;

    return MinItem;
}