数据结构与算法：堆的操作集

大家好，欢迎来到IT知识分享网。

数据结构与算法：堆的操作集

堆是一种特殊的数据结构，类似于优先队列，也就是说其中的元素是具有优先级的。堆在计算机CPU分配时有应用，比如对于控制核反应的电脑，控制的调度优先级大于其他的程序，每次从队列中取出的元素都是整个堆中最大的。
堆的实现方法是采用类似二叉树的结构，这个二叉树用数组来存储。
堆按照根节点和子节点的大小关系分为最大堆和最小堆，下面以最大堆为例，给出堆的操作集。

#include<stdio.h> #include<cstdlib> #define MaxData 1000 typedef struct HeapStruct *MaxHeap; typedef int ElementType; struct HeapStruct{ 
    ElementType *Elements; int Size; int Capacity; }; //基本操作 bool IsFull(MaxHeap H); bool IsEmpty(MaxHeap H); MaxHeap Create(int MaxSize); //构建一个空堆，容量为MaxSize void Insert(MaxHeap H, ElementType item); //插入操作 ElementType DeleteMax(MaxHeap H); //删除操作 void display(MaxHeap H); //打印 //建立堆的技巧 void BuildHeap(MaxHeap H); //通过一个未排序的堆来建立堆 void PercDown(MaxHeap H, int p); //调整堆 bool IsFull(MaxHeap H) { 
    return (H->Size >= H->Capacity); } bool IsEmpty(MaxHeap H) { 
    return (H->Size == 0); } MaxHeap Create(int MaxSize) { 
    MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapStruct)); H->Elements = (ElementType*)malloc((MaxSize+1)*sizeof(ElementType)); H->Capacity = MaxSize; H->Size = 0; H->Elements[0] = MaxData; //哑结点，要求比所有值都要大，方便插入操作 return H; } void Insert(MaxHeap H, ElementType item) { 
    if(IsFull(H)) { 
   printf("Full"); return;} //先插到队尾，然后与父节点进行比较，如果大于父节点，两者交换 int i = ++H->Size; for(;item > H->Elements[i/2]; i/=2) H->Elements[i] = H->Elements[i/2]; H->Elements[i] = item; } ElementType DeleteMax(MaxHeap H) { 
    //思路是要删除根节点，然后用最后一个节点来替换 if(IsEmpty(H)) { 
   printf("Empty"); return 0;} ElementType MaxElem, temp; //temp指向最后一个元素 int parent, child; //parent记录最后一个元素应该插入的位置 temp = H->Size--; MaxElem = H->Elements[1]; //找插入点的过程 for(parent = 1; 2*parent <= H->Size; parent = child){ 
    child = 2*parent; if(child != H->Size && H->Elements[child] < H->Elements[child+1]) //使child成为子节点中的较大值 child++; if(temp > H->Elements[child]) break; //如果temp比子节点大，那么退出循环，父节点parent就是插入的位置 else H->Elements[parent] = H->Elements[child]; //否则子节点取替换根节点，继续往下寻找 } H->Elements[parent] = temp; return MaxElem; } void display(MaxHeap H) { 
    for(int i = 1; i <= H->Size; i++) printf("%d ", H->Elements[i]); printf("\n"); } //通过调整一个普通的二叉树建立堆 void BuildHeap(MaxHeap H) { 
    int i; for(i = H->Size/2; i > 0; i--) //从最下层的父节点开始，依次往上 PercDown(H, i); } //调整以p为根节点序号的二叉树，使其成为堆 void PercDown(MaxHeap H, int p) { 
    int parent, child; ElementType item = H->Elements[p]; //取出根节点的值，调整以后找到位置插入 for(parent = p; 2*parent <= H->Size; parent = child){ 
    child = parent*2; if(child!=H->Size && H->Elements[child] < H->Elements[child+1]) child++; if(item > H->Elements[child]) break; else H->Elements[parent] = H->Elements[child]; } H->Elements[parent] = item; }