最大堆（优先队列）基本概念，即一个完整建立，插入，删除代码

╰半夏微凉° 2021-12-17 10:01 170阅读 0赞

堆（优先队列）priority queue  
特殊的队列，取出元素的顺序是依照元素的优先权（关键字）大小，而出元素进入队列的先后顺序  
操作：查找最大值（最小值），删除（最大值）

数组：  
链表：  
有序数组：  
有序链表：

采用二叉搜索树？ NO

采用完全二叉树 YES  
堆的连个特性  
结构性：用数组表示的完全二叉树：  
有序性：任一结点的关键字是其字树所有结点的最大值（或最小值）  
 最大堆（MaxHeap）也称大顶堆：最大值  
 最小堆（MinHeap）也称“小顶堆”：最小值  
 从根节点到任意结点路径上结点序列的有序性  
操作：插入任意一个元素，删除最 大值元素  
最大堆的删除：取出根节点（最大值）元素，同时删除堆的一个结点

最大堆的建立：将已存在的N个元素按最大堆的要求存放在一个以为数组中

1 #include <stdio.h>
     2 #include <stdlib.h>
     3 //最大堆
     4 
     5 #define MaxData 1000        //哨兵，该值应该根据具体情况定义为大于堆中所有可能元素的值
     6 
     7 typedef int ElementType;
     8 
     9 typedef struct HeapNode * MaxHeap;
    10 struct HeapNode {
    11     int Capacity;            //堆的最大容量
    12     int Size;                //堆中当前元素个数
    13     ElementType *Data;    //用于存储元素的数组
    14 };

建一个空的最大堆：

1 //建立一个空的最大堆
     2 MaxHeap InitHeap(int maxsize)
     3 {
     4     MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapNode));
     5     H->Data = (ElementType*)malloc(sizeof(struct HeapNode) * (maxsize + 1));        //堆中的元素是从下标为1开始存储的，但是为了保证这个堆能存下maxsize个元素，所以要分配maxsize + 1个内存单元
     6     H->Capacity = maxsize;
     7     H->Size = 0;
     8     H->Data[0] = MaxData;            //将0下标的单元存储哨兵
     9     for (int i = 1; i < maxsize + 1; i++)
    10         H->Data[i] = 0;
    11     return H;
    12 }

判断堆是否已满或是否为空：

1 int IsEmpty(MaxHeap H)
     2 {
     3     return H->Size == 0;
     4 }
     5 
     6 //判断堆是否已满
     7 int IsFull(MaxHeap H)
     8 {
     9     return H->Size == H->Capacity;
    10 }

插入一个元素：

1 //最大堆中插入一个元素
     2 void Insert(MaxHeap H, ElementType item)
     3 {
     4     int i;
     5     if (IsFull(H))
     6     {
     7         printf("The heap is full\n");
     8         return;
     9     }
    10     i = ++H->Size;        //i为插入后堆中最后一个元素的位置
    11     for (; H->Data[i / 2] < item; i /= 2)
    12         H->Data[i] = H->Data[i / 2];        //循环退出时，父节点的数据已经大于item， item已经找到了正确的位置
    13     H->Data[i] = item;    //将item赋给正确的下标单元
    14 }

删除一个元素：

1 ElementType Delete(MaxHeap H)
     2 {
     3     ElementType temp, Max;
     4     int parent = 1, child;
     5     if (IsEmpty(H))
     6     {
     7         printf("The heap is empty!\n");
     8         return 0;
     9     }
    10     Max = H->Data[1];            //现将最大值即根节点的值记录下来
    11     temp = H->Data[H->Size--];        //用最后的结点元素暂时代替根节点的数据，然后将堆的数据大小减1
    12 
    13     //如果2 * parent > 0，那么说明parent已经是根节点了
    14     for (; 2 * parent <= H->Size; parent = child)
    15     {
    16         child = 2 * parent;
    17 
    18         //如果Child != H->Size说明child不是最后一个结点，该parent结点还有右节点，
    19         //并且如果右节点的值大于左结点，那么child++;
    20         if (child != H->Size && (H->Data[child + 1] < H->Data[child]))
    21             child++;        //child指向左右子节点的较大者
    22         if (temp > H->Data[child]) break;            //如果孩子结点已经小于temp了， 说明找到了合适的位置
    23         else
    24             H->Data[parent] = H->Data[child];
    25     }
    26     H->Data[parent] = temp;
    27     return Max;
    28 }

最大堆的建立：

1.第一步，将N个元素按输入顺序存入二叉树中，这一步需要求满足完全二叉树的结构特性，而不管其有序性

2.从最后一个右孩子的结点开始调整，做类似删除元素时的下滤操作，逐个结点调整，直至根节点

1 //创建一个最大堆
     2 MaxHeap CreateMaxHeap()
     3 {
     4     int dt, i = 0, j;
     5     int parent, child;
     6     ElementType X;
     7     MaxHeap H = InitHeap(20);        //先创建一个空的最大堆，然后往里面填充元素
     8     while (scanf_s("%d", &dt) != EOF)
     9     {
    10         H->Data[i + 1] = dt;
    11         i++;
    12         H->Size++;
    13     }
    14     for (j = i / 2; j >= 1; j--)        //从i / 2开始逐一向下过滤
    15     {
    16         //下面的操作和删除元素是一模一样的，只是不用将的元素个数减一
    17         X = H->Data[j];
    18         for (parent = j; 2 * parent <= H->Size; parent = child)
    19         {
    20             child = 2 * parent;
    21             if (child != H->Size && H->Data[child] < H->Data[child + 1])
    22                 child++;
    23             if (H->Data[child] < X)
    24                 break;
    25             else
    26                 H->Data[parent] = H->Data[child];
    27         }
    28         H->Data[parent] = X;
    29     }
    30     return H;
    31 }

打印堆中的元素：

1 //打印堆中元素
    2 void printHeap(MaxHeap H)
    3 {
    4     for (int i = 1; i <= H->Size; i++)
    5         printf("%d ", H->Data[i]);
    6     printf("\n");
    7 }

先序建立树：

1 void PreOrderCreateHeap(MaxHeap H, int index)
     2 {
     3     int dt;
     4     scanf_s("%d", &dt);
     5     if (dt == 0)
     6     {
     7         return;
     8     }
     9     H->Size++;
    10     H->Data[index] = dt;
    11     printf("please enter the left child of %d :", dt);
    12     PreOrderCreateHeap(H, 2 * index);
    13     printf("please enter the right child of %d: ", dt);
    14     PreOrderCreateHeap(H, 2 * index + 1);
    15 }

主函数：

1 int main()
    2 {
    3     MaxHeap H = CreateMaxHeap();
    4     PreOrderCreateHeap(H, 1);
    5     printHeap(H);
    6 
    7     return 0;
    8 }

转载于:https://www.cnblogs.com/hi3254014978/p/9527060.html