堆（C语言） – 小飞侠

文章目录

堆(heap)

堆(heap)

什么是堆

定义

堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
性质
1. 结构性：用数组表示的完全二叉树。
2. 有序性：任意节点的关键字（权值）是其子树所有节点的最大值（或最小值）
  - 父节点大于子节点：最大堆(MaxHeap)
  - 父节点小于子节点：最小堆(MinHeap)
应用
1. 优先队列
  
  “优先队列” （Priority Queue）是特殊的“队列”，从队列中取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。
2. 堆排序
举例
1. 堆：最大堆或最小堆
2. 不是堆：不是完全二叉树或节点权值不符合要求

最小堆的操作

数据名称

：最小堆(MinHeap)
数据对象集

：

一个有
$\gt 0 N > 0 个元素的最小堆是一棵完全二叉树，每个节点上的元素值不大于其子节点元素的值。$
操作集

：

对于任意最多有MaxSize个元素的最小堆
H

∈

M

i

n

H

e

a

p

H \in MinHeap

$H \in M i n H e a p$

元素

t

e

m

∈

E

l

e

m

e

n

t

T

y

p

e

item \in ElementType

$i t e m \in E l e m e n t T y p e$

，主要操作有：
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语言)

数组表示的完全二叉树

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

例：

由子节点找父节点：父节点下标=子节点下标 / 2

由父节点找左子节点：左子节点下标=父节点下标 * 2

由父节点找右子节点：右子节点下标=父节点下标 * 2 + 1

存储结构

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

操作集的实现

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;
}

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

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

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

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

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

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

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;
}

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;
}

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;
}

原文链接：https://blog.csdn.net/qq_42313728/article/details/104033501

文章目录

堆(heap)

什么是堆

最小堆的操作

操作集的实现(C语言)

你可能也喜欢