堆（C语言）

堆(heap)

什么是堆

1. 定义

   堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。

2. 性质

   1. 结构性：用数组表示的完全二叉树。
   2. 有序性：任意节点的关键字（权值）是其子树所有节点的最大值（或最小值）
      • 父节点大于子节点：最大堆(MaxHeap)
      • 父节点小于子节点：最小堆(MinHeap)

3. 应用

   1. 优先队列

      “优先队列” （Priority Queue）是特殊的“队列”，从队列中取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。

   2. 堆排序

4. 举例

   1. 堆：最大堆或最小堆
      
   2. 不是堆：不是完全二叉树或节点权值不符合要求
      

最小堆的操作

1. 数据名称：最小堆(MinHeap)
2. 数据对象集：
   一个有 N > 0 N \gt 0 N>0个元素的最小堆是一棵完全二叉树，每个节点上的元素值不大于其子节点元素的值。
3. 操作集：
   对于任意最多有MaxSize个元素的最小堆 H ∈ M i n H e a p H \in MinHeap H∈MinHeap元素 i t e m ∈ E l e m e n t T y p e item \in ElementType item∈ElementType，主要操作有：
   1. MinHeap Create(int Maxsize): 创建一个空的最小堆。
   2. void Destroy(MinHeap)：释放堆的空间。
   3. Boolean IsFull(MinHeap H): 判断最小堆是否已满。
   4. Boolean IsEmpty(MinHeap H): 判断最小堆是否为空。
   5. void Insert(MinHeap H,ElementType item): 将元素item插入最小堆H。
   6. ElementType DeleteMin(MinHeap H): 返回最小堆H中最小元素（高优先级）。

操作集的实现(C语言)

1. 数组表示的完全二叉树
   数组下标为0的位置放一个比所有堆中元素都要小的元素（可以是ElementType的最小值），称为“哨兵”。从下标为1的位置开始存放堆中元素。因为是完全二叉树，所以父亲节点与其左右子节点下标满足一些关系。
   例：
   
   由子节点找父节点：父节点下标=子节点下标 / 2
   由父节点找左子节点：左子节点下标=父节点下标 * 2
   由父节点找右子节点：右子节点下标=父节点下标 * 2 + 1

2. 存储结构

   typedef struct HeapStruct{
     ElementType *Element; /* 存储堆元素的数组 */
     int Size; /* 堆的当前元素个数（最后一个元素的下标） */
     int MaxSize; /* 堆存储空间的大小 */
   }HeapStruct,*MinHeap;
   

3. 操作集的实现

   1. MinHeap Create(int MaxSize): 创建一个空的最小堆

      MinHeap Create(int MaxSize)
      {
        MinHeap H = (MinHeap)malloc(sizeof(struct HeapStruct));//分配堆结构空间
        H->Elenment = (ElementType *)malloc((MaxSize + 1) * sizeof(ElementType));//分配储存堆元素的数组的空间
        H->Size = 0;
        H->MaxSize=MaxSize;
        H->Elenment[0] = INT_MIN;//数组第一个元数放最小元素，数组第二个元素放堆中最小元素
      
        return H;
      }
      

   2. void Destroy(MinHeap H): 释放堆申请的空间

      void Destroy(MinHeap H)
      {
        free(H->Elenment);//先释放堆节点的数组空间
        free(H);//再释放堆节点的空间
      }
      

   3. boolean IsFull(MinHeap H): 判断最小堆是否已满

      boolean IsFull(MinHeap H)
      {
        return (H->Size == H->MaxSize);//判断最小堆中元素个数Size是否等于最大容量MAXSIZE。
      }
      

   4. boolean IsEmpty(MinHeap H): 判断最小堆是否为空

      boolean IsEmpty(MinHeap H)
      {
        return (H->Size == 0);//判断堆中元素个数是否等于0
      }
      

   5. void Insert(MinHeap H,ElementType item): 将元素item插入最小堆H

      //将元素item插入堆H
      void Insert(MinHeap H, ElementType item)
      {
        int i = 0;
      
        //判断堆H是否已满
        if (IsFull(H))
        {
          printf("Heap is full\n");
          return;
        }
      
        /*
        如果H未满，将item放入堆最后一个元素，查看它的父节点，如果它的父节点比它大，将它和它的父节点互换位置，
        循环此过程，直至它的父节点小于它。可能它比所有它的父节点都要小，但是一定会比哨兵大（数组中下标为0的位置），
        所以一定最后它的下标一定大于哨兵的下标0。这就是哨兵的意义。
        */
        H->Size++;
        for (i = H->Size; H->Element[i / 2] > item; i = i / 2)
        {
          H->Element[i] = H->Element[i / 2];
        }
        H->Element[i] = item;
      }
      

   6. ElementType Delete(MinHeap H): 返回最小堆H中最小元素（高优先级）

      //将堆根节点元素取出，并将堆元素重新排序
      ElementType Delete(MinHeap H)
      {
        int parent=0,child=0;
        ElementType item,temp;
      
        //判断堆是否已经空了
        if (IsEmpty(H))
        {
          printf("Heap is Empty\n");
          return H->Element[0];
        }
      
        /*
        堆没有空，将根节点返回，最后一个叶子节点放到根节点位置，然后比较它与它的左右子节点中最小
        节点的大小，如果它比较大，则将它和它的较小的子节点互换位置，重复此过程，直至他比两个子节点
        都小或者它不在有子节点
        */
        item = H->Element[1];
        temp = H->Element[H->Size];
        H->Size--;
        for (parent = 1; parent *2 <= H->Size; parent = child)
        {
          child = parent *2;
          //找出左右子节点最小的那个
          if (child != H->Size && (H->Element[child] > H->Element[child + 1]))
          {
            child++;
          }
          //比较它与最小的子节点的大小，如果它比较大，则两者互换位置，否则跳出循环
          if (temp > H->Element[child])
          {
            H->Element[parent] = H->Element[child];
          }
          else
          {
            break;
          }
        }
        H->Element[parent] = temp;
        return item;
      }
      

   7. MinHeap BuildMinHeap(ElementType *Elenment, int Size): 创建一个非空的堆

      已知堆中元素，但是不知道其在数组中的排列顺序，可以有两种创建堆的方法：一是先创建一个空堆，再使用Insert()函数将元素一个个插入堆中。二是直接将数组复制到堆节点的Element数组中，然后进行排序。

      第二种方法比第一种方法时间复杂度更低。

      //已知一个数组，创建一个由数组元素组成的最小堆
      MinHeap BuildMinHeap(ElementType *Element, int Size,int MaxSize)
      {
        MinHeap H = NULL;
        int i = 0, parent = 0, child = 0;
        ElementType Temp;
      
        //创建一个空最小堆
        H = CreateMinHeap(MaxSize);
      
        //判断存储空间是否够用
        if (Size > H->MaxSize)
        {
        	printf("最小堆存储空间不足，建立最小堆失败\n");
        	return NULL;
        }
      
        //将数组中元素复制到存储最小堆元素的数组里
        for (i = 0; i < Size; i++)
        {
        	H->Element[i + 1] = Element[i];
        }
        H->Size = Size;
      
        //给最小堆存储空间中元素排序
        /*
        最后一个节点的父节点的左右指针都指向一个堆，将最后一个节点的父节点和它的两个子节点排序（方法类似
        与删除节点的操作），使得最后一个节点、其父节点和其兄弟节点形成一个堆。循环操作，从最后一个节点的
        父节点往上依次执行这个操作，最后使得整个树都是一个堆。
        */
        for (parent = H->Size / 2; parent >= 1; parent--)
        {
        	Temp = H->Element[parent];
        	for (; parent * 2 <= H->Size; parent = child)
        	{
        		child = parent * 2;//child为parent左子树的下标，(child+1)为右子树下标
      
        		//如果左右子树都存在，且左子树大于右子树的值，将child作为两者较小者的下标
        		if (child != H->Size && (H->Element[child] > H->Element[child + 1]))
        		{
        			child++;
        		}
      
        		//比较parent指向的节点与child指向节点的大小，parent较大则两者互换位置
        		if (Temp > H->Element[child])
        		{
        			H->Element[parent] = H->Element[child];
        		}
        		else
        		{
        			break;
        		}
        	}
        	H->Element[parent] = Temp;
        }
      
        return H;
      }