## 1. 二叉堆

1. 链表
2. 二叉查找树
3. 二叉堆的数组实现 堆是完全二叉树，它的堆序性

### 优先队列的声明：

``````#ifndef BINHEAP_BINHEAP_H
#define BINHEAP_BINHEAP_H

struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

PriorityQueue Init(int MaxElements);
void Destroy(PriorityQueue H);
void MakeEmpty(PriorityQueue H);
void Insert(int X, PriorityQueue H);
int DeleteMin(PriorityQueue H);
int FindMin(PriorityQueue H);
int IsEmpty(PriorityQueue H);
int IsFull(PriorityQueue H);
#endif //BINHEAP_BINHEAP_H
struct HeapStruct{
int Capactiy;
int Size;
int *Elems;
};
``````

### 初始化以及销毁：

``````PriorityQueue Init(int MaxElements){
PriorityQueue H;
H = malloc(sizeof(struct HeapStruct));
H->Elems = malloc(sizeof(int)* (MaxElements + 1));
H->Size = 0;
H->Capactiy = MaxElements;
H->Elems[0] = -9999;
return H;
}

void Destroy(PriorityQueue H){
free(H->Elems);
free(H);
}
``````

### 插入：

``````void Insert(int X, PriorityQueue H){
int i;
if (IsFull(H)){
return;
}
for(i = ++H->Size;H->Elems[i/2] > X; i /=2){
H->Elems[i] = H->Elems[i/2];
}
H->Elems[i] = X;
H->Elems[0] = H->Elems[1];
}
``````

### 删除最小元：

``````int DeleteMin(PriorityQueue H){
int i,child;
if (IsEmpty(H))
return H->Elems[0];
int X = H->Elems[H->Size--];
int Min = H->Elems[1];

for(i = 1; i * 2 <= H->Size; i = child){
child = i * 2;
if (child != H->Size && H->Elems[child + 1] < H->Elems[child]){
child ++;
}
if (H->Elems[child] < X)
H->Elems[i] = H->Elems[child];
else
break;
}
H->Elems[i] = X;
return Min;
}
``````

### 构建二叉堆-BUildHeap

``````PriorityQueue BuildHeap(int *A, int N){
PriorityQueue H;
H = malloc(sizeof(struct HeapStruct));
H->Size = N;
H->Capactiy = N;
H->Elems = malloc(sizeof(int) * (N + 1));
int i;
for( i = N/2; i > 0; i--){
PercolateDown(i,A,N);
}
for (int j = 1; j <= N; ++j) {
H->Elems[j] = A[j];
}
return H;
}
``````

``````void PercolateDown(int index, int *A,int N){
int child;
int t;
for( int i = index; i*2<=N; i = child){
child = i * 2;
if (child != N && A[child] > A[child + 1])
child++;
if(A[child] < A[i]){
t = A[i];
A[i] = A[child];
A[child] = t;
}
}
}
``````

## 2. 左式堆

1. 任一节点的NPL比所有儿子节点的NPL的最小值多1
2. 最小堆的特性：父节点属性值小于子节点属性值
3. 堆中任一节点的左儿子的NPL >= 右儿子的NPL

### 左式堆节点结构

``````struct TreeNode{
int Elem;
PriorityQueue Left;
PriorityQueue Right;
int Npl;
};
``````

### 左式堆的基本操作是合并，O(logN)

1. 如果有一个堆是空树，直接返回另一个堆，否则根节点值大的堆和根节点值小的右子树递归合并，形成新的左式堆
2. 合并后的新堆作为较小堆的右子树
3. 如果堆根节点的NPL不符合左式堆的特性，交换左右子树
4. 更新根节点的NPL

``````PriorityQueue Merge(PriorityQueue H1, PriorityQueue H2){
if (H1 == NULL)
return H2;
if (H2 == NULL)
return H1;
if (H1->Elem < H2->Elem)
return Merge1(H1,H2);
else
return Merge1(H2,H1);
}

PriorityQueue Merge1(PriorityQueue H1, PriorityQueue H2){
if (H1->Left == NULL)// H1是单节点
H1->Left = H2;
else{
H1->Right = Merge(H1->Right,H2);
if (H1->Left->Npl < H1->Right->Npl)
SwapChildren(H1);
H1->Npl = H1->Right->Npl + 1;
}
return H1;
}
``````

### 插入操作可以看成单节点堆和另一个堆合并的情况，O(logN)

``````PriorityQueue Insert(int X, PriorityQueue H){
Node P;
P = malloc(sizeof(struct TreeNode));
P->Elem = X;
P->Left = P->Right = NULL;
P->Npl = 0;
H = Merge(P,H);
return H;
}
``````

### 删除最小数操作直接删除根节点，将左右子树合并形成新的左式堆,O(logN)

``````PriorityQueue DeleteMin(PriorityQueue H){
PriorityQueue LeftHeap,RightHeap;
if (IsEmpty(H))
return NULL;
else{
LeftHeap = H->Left;
RightHeap = H->Right;
free(H);
return Merge(LeftHeap,RightHeap);
}
}
``````

### 其它操作(上滤，增加或降低关键字值)

``````void PercolateUp(int index, int *A){
int parent;
for (int i = index; i / 2>0 ; i /=2) {
parent = i/2;
if (A[parent] > A[index]){
int t = A[parent];
A[parent] = A[index];
A[index] = t;
}
else
break;
}
}

void DecreaseKey(int index, int Incre, int *A){
A[index] -=Incre;
PercolateUp(index,A);
}
void IncreaseKey(int index, int Incre, int *A,int N){
A[index] +=Incre;
PercolateDown(index,A,N);
}
``````

## 3. 斜堆

1. 如果一个是空堆，直接返回一个另一个斜堆
2. 两个斜堆都非空，那么比较两个根节点，取较小堆的根节点作为新的根节点，较小堆根节点的右子树与较大堆递归合并
3. 交换根的左右子树

1. 如果堆根节点的NPL不符合左式堆的特性，交换左右子树
2. 更新根节点的NPL

## 4. 二项队列

### 二项队列操作

``````struct BinNode{
int Elem;
Position LeftChild;
Position NextSibling;
};
struct Collection{
int CurrentSize;
BinTree TheTrees[MaxSize];
};
``````

#### 合并

``````BinTree CombineTrees(BinTree T1,BinTree T2){
if(T1->Elem > T2->Elem)
return CombineTrees(T2,T1);
T2->NextSibling = T1->LeftChild;
T1->LeftChild = T2;
return T1;
}
``````

``````BinQueue Merge(BinQueue H1, BinQueue H2){
BinTree T1,T2,Carry = NULL;
int i,j;
H1->CurrentSize += H2->CurrentSize;
for (int i = 0,j=1; j < H1->CurrentSize; ++i,j*=2) {
T1 = H1->TheTrees[i];
T2 = H2->TheTrees[i];
switch (!!T1 + 2*!!T2 + 4*!!Carry){
case 0://没有树
case 1://只H1存在
break;
case 2://只H2存在
H1->TheTrees[i] = H2;
H2->TheTrees[i] = NULL;
break;
case 3://H1和H2存在
Carry = CombineTrees(T1,T2);
H1->TheTrees[i] = H2->TheTrees[i] = NULL;
break;
case 4://H1和H2不存在，Carry存在
H1->TheTrees[i] = Carry;
Carry = NULL;
break;
case 5://H1和Carray
Carry = CombineTrees(T1,Carry);
H1->TheTrees[i] = NULL;
break;
case 6://H2和Carry
Carry = CombineTrees(T2,Carry);
H2->TheTrees[i] = NULL;
break;
case 7://H1,H2和Carry都存在
H1->TheTrees[i] = Carry;
Carry = CombineTrees(T1,T2);
H2->TheTrees[i] = NULL;
break;
}
}
return H1;
}
``````

#### 插入

``````BinQueue Insert(int Item, BinQueue H) {
BinTree NewNode;    //二项树B0
BinQueue OneItem;   //只有B0的二项队列
NewNode = malloc(sizeof(struct BinNode));
NewNode->Elem = Item;
NewNode->LeftChild = NewNode->NextSibling = NULL;
OneItem = Init();
OneItem->CurrentSize = 1;
OneItem->TheTrees[0] = NewNode;
return Merge(H, OneItem);   //合并单节点的二项树构成的二项队列与H
}
``````

#### 删除最小元

``````int DeleteMin(BinQueue H){
int i,j;
int index;// array index;
BinQueue DeletedQueue;
Position DeletedTree, OldToot;
int Min;
Min = 9999;
for (int k = 0; k < 10; ++k) {
if(H->TheTrees[k] && H->TheTrees[k]->Elem < Min){
index = k;
Min = H->TheTrees[k]->Elem;
}
}
DeletedTree = H->TheTrees[index];//指向当前最小根节点二项树
OldToot = DeletedTree;
DeletedTree = DeletedTree->LeftChild;
free(OldToot);

DeletedQueue = Init();
DeletedQueue->CurrentSize = (1<<index) - 1;
for(j = index - 1; j >= 0; j--){
DeletedQueue->TheTrees[j] = DeletedTree;
DeletedTree = DeletedTree->NextSibling;
DeletedQueue->TheTrees[j]->NextSibling = NULL;
}
H->TheTrees[index] = NULL;
H->CurrentSize -=DeletedQueue->CurrentSize + 1;
Merge(H,DeletedQueue);
return Min;
}
``````