堆，堆的创建，插入，删除，建立

什么是堆

优先队列&＃xff08; &＃xff08;Priority Queue &＃xff09;&＃xff1a;特殊的“ 队列” &＃xff0c;取出元素的顺序是依照元素的 优先权&＃xff08;关键字&＃xff09;大小&＃xff0c;而不是元素进入队列的先后顺序。

优先队列的完全二叉树表示

bool Insert(MaxHeap H, Elemtype X)
{ /* 将元素X插入最大堆H&＃xff0c;其中H->Data[0]已经定义为哨兵 */int i;if (IsFull(H)){printf("最大堆已满");return false;}i &＃61; &＃43;&＃43;H->Size; /* i指向插入后堆中的最后一个元素的位置 */for (; H->Data[i / 2] < X; i /&＃61; 2)H->Data[i] &＃61; H->Data[i / 2]; /* 上滤X */H->Data[i] &＃61; X; /* 将X插入 */return true;
}


H->Element[ 0 ] 是哨兵元素&＃xff0c;它不小于堆中的最大元素。当插入的元素比任意元素都大&＃xff0c;哨兵的存在使得H->Elements[0] > item; 顺环结束。
时间复杂度&＃xff1a; O(log N)

最大堆的删除

取出根结点&＃xff08;最大值&＃xff09;元素&＃xff0c;同时删除堆的一个结点。
用最后一个结点代替根结点&＃xff0c;取根结点两孩子的较大的一个&＃xff0c;若较大值大于此时的根节点&＃xff0c;将该较大值移动至根结点&＃xff0c;不断重复&＃xff0c;直到找到最后一个结点该插入的位置。

完整c&＃43;&＃43;代码

#include
#include
using namespace std;#define Elemtype int
#define MAXDATA 1000 /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */typedef struct HNode {Elemtype *Data; /* 存储元素的数组 */int Size; /* 堆中当前元素个数 */int Capacity; /* 堆的最大容量 */
}*Heap;typedef Heap MaxHeap; /* 最大堆 */
typedef Heap MinHeap; /* 最小堆 */MaxHeap CreateHeap(int MaxSize)
{ /* 创建容量为MaxSize的空的最大堆 */MaxHeap H &＃61; (MaxHeap)malloc(sizeof(struct HNode));H->Data &＃61; (Elemtype *)malloc((MaxSize &＃43; 1)*sizeof(Elemtype));H->Size &＃61; 0;H->Capacity &＃61; MaxSize;H->Data[0] &＃61; MAXDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/return H;
}bool IsFull(MaxHeap H)
{return (H->Size &＃61;&＃61; H->Capacity);
}bool Insert(MaxHeap H, Elemtype X)
{ /* 将元素X插入最大堆H&＃xff0c;其中H->Data[0]已经定义为哨兵 */int i;if (IsFull(H)){printf("最大堆已满");return false;}i &＃61; &＃43;&＃43;H->Size; /* i指向插入后堆中的最后一个元素的位置 */for (; H->Data[i / 2] < X; i /&＃61; 2)H->Data[i] &＃61; H->Data[i / 2]; /* 上滤X */H->Data[i] &＃61; X; /* 将X插入 */return true;
}#define ERROR -1 /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */bool IsEmpty(MaxHeap H)
{return (H->Size &＃61;&＃61; 0);
}Elemtype DeleteMax(MaxHeap H)
{ /* 从最大堆H中取出键值为最大的元素&＃xff0c;并删除一个结点 */int Parent, Child;Elemtype MaxItem, X;if (IsEmpty(H)) {printf("最大堆已为空");return ERROR;}MaxItem &＃61; H->Data[1]; /* 取出根结点存放的最大值 *//* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */X &＃61; H->Data[H->Size--]; /* 注意当前堆的规模要减小 */for (Parent &＃61; 1; Parent * 2 <&＃61; H->Size; Parent &＃61; Child){Child &＃61; Parent * 2;if ((Child !&＃61; H->Size) && (H->Data[Child]<H->Data[Child &＃43; 1]))Child&＃43;&＃43;; /* Child指向左右子结点的较大者 */if (X >&＃61; H->Data[Child]) break; /* 找到了合适位置 */else /* 下滤X */H->Data[Parent] &＃61; H->Data[Child];}H->Data[Parent] &＃61; X;return MaxItem;
}/*----------- 建造最大堆 -----------*/
void PercDown(MaxHeap H, int p)
{ /* 下滤&＃xff1a;将H中以H->Data[p]为根的子堆调整为最大堆 */int Parent, Child;Elemtype X;X &＃61; H->Data[p]; /* 取出根结点存放的值 */for (Parent &＃61; p; Parent * 2 <&＃61; H->Size; Parent &＃61; Child) {Child &＃61; Parent * 2;if ((Child !&＃61; H->Size) && (H->Data[Child]<H->Data[Child &＃43; 1]))Child&＃43;&＃43;; /* Child指向左右子结点的较大者 */if (X >&＃61; H->Data[Child]) break; /* 找到了合适位置 */else /* 下滤X */H->Data[Parent] &＃61; H->Data[Child];}H->Data[Parent] &＃61; X;
}void BuildHeap(MaxHeap H)
{ /* 调整H->Data[]中的元素&＃xff0c;使满足最大堆的有序性 *//* 这里假设所有H->Size个元素已经存在H->Data[]中 */int i;/* 从最后一个结点的父节点开始&＃xff0c;到根结点1 */for (i &＃61; H->Size / 2; i>0; i--)PercDown(H, i);
}int main()
{Heap heap &＃61; CreateHeap(20);int a[13] &＃61; { MAXDATA, 79, 66, 43, 83, 30, 87, 38, 55, 91, 72, 49, 9 };int len &＃61; sizeof(a) / sizeof(a[0]);heap->Data &＃61; a;heap->Size &＃61; len-1;BuildHeap(heap);for (int i &＃61; 1; i <&＃61; heap->Size; i&＃43;&＃43;)cout << heap->Data[i]<<" ";cout << endl << endl;cout << DeleteMax(heap) << endl;for (int i &＃61; 1; i <&＃61; heap->Size; i&＃43;&＃43;)cout << heap->Data[i] << " ";cout << endl << endl;if (Insert(heap, 99)){for (int i &＃61; 1; i <&＃61; heap->Size; i&＃43;&＃43;)cout << heap->Data[i] << " ";}
}