【数据结构】模拟实现 堆

堆数据结构是一种数组对象，它可以被看作一颗完全二叉树的结构（数组是完全二叉树），堆是一种静态结构。

堆分为最大堆和最小堆。

最大堆：每个父结点都大于孩子结点。

最小堆：每个父结点都小于孩子结点。

堆的优势：效率高，可以找最大数最小数，增删的时间复杂度为lgN

怎么找最后一个叶子结点？

找到最后一个叶子结点（左孩子为空就是叶子结点），由于堆是静态结构，所以我们要通过计算下标的方法找，计算它的孩子是否超出了数组范围。

通过观察可以总结数组下标计算父子关系的公式：

leftchild = parent*2 +1

rightchild = parent*2+ 1

parent =( child -1) /2

1.代码实现：

typedef  int  HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;}HP;

Heap结构体中有一个指向动态数组的指针，size表示数组的当前元素个数，capacity表示数组的容量

将结构体的定义和函数的申明都放在Heap.h中：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef  int  HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;}HP;//以数组的形式打印堆的元素
void PrintHeap(HP* php);
//初始化堆
void HeapInit(HP* php);
//销毁
void HeapDestory(HP* php);//插入数据x 但是要依旧保持堆的形态
void HeapPush(HP* php, HPDataType x);//删除堆顶的元素
void HeapPop(HP* php);//返回堆顶的元素
HPDataType HeapTop(HP* php);
//判定堆是否为空
bool HeapEmpty(HP* php);
//返回堆当前元素的个数
int HeapSize(HP* php);

在Heap.c文件中完成接口的实现：

初始化：

void HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;}

插入元素：

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0)  {if (a[child] < a[parent])    {Swap(&a[child], &a[parent]);  child = parent;         parent = (child - 1) / 2;   }else     {break;}}
}
void HeapPush(HP* php, HPDataType x) 
{assert(php);if (php->size == php->capacity)  //检查容量{int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(-1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);   
}

HeapPush函数：：插入元素将对象的指针传过来并且将要插入的元素传过来，插入元素前检查容量当size ==capacity时就得扩容，我们采用的是将原来的容量扩大两倍，因为两倍比较合适。定义一个新的容量当之前的容量为0时给4个字节的大小，之前有容量时扩大到原来的两倍。这里需要注意的时realloc是在原来的基础上扩大的字节数所以要记得newcapacity*sizeof(HPDataType)!再将a指向扩容后的地址然后更新capacity的大小，在size位置插入元素x，然后size++。在这里模拟实现的是小堆，但是插入数据的位置在逻辑结构的数组的尾部，或者说是在完全二叉树的叶子节点位置。小堆结构的最小的元素都在较上方，所以说要向上调整。将数组的指针和插入元素的数组下标传给向上调整函数。

AdjustUp函数：：通过公式计算出插入元素的数组下标的父节点的数组下标。

假设插入的位置在最下方的红色部分，小堆就是父节点要比子节点的值小，如果插入的元素的值很小，需要一直和当前位置的父节点交换位置，那交换最多的情况就是从叶子节点的位置交换到根节点的位置(也就是说child=0时），因为交换的次数不确定所以放到for不好控制，所以将向上调整的动作放到while循环里，当符合条件时跳出循环即可。当child>0时,a[child] < a[parent]所以进行交换，将parent的下标的值给child，然后再次计算出该节点位置的父节点的数组下标，再次比较该节点与其父节点的值的大小，如果符合调整的条件就进行交换，一直循环。当child==0或者a[parent]>=a[parent]的值就不需要就跳出循环，向上调整结束，新插入的元素就到了应该到的位置。

Swap函数：：取出要交换的值的地址交给该函数，创建一个同类型的变量tmp存储p1指向的内容，p1再指向p2所指向的内容，最后再将p2指向tmp就完成了值的交换。

通过这三个函数就完成了数据的插入，同时保持了堆的形态。

删除堆顶的元素：

首先明白小堆和大堆的应用时为了找到前n个最小或者最大的元素，删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

void AdjustDown(HPDataType* a, int n, int parent) 
{int minChild = parent * 2 + 1;   //默认最小的孩子是左孩子while (minChild < n){if (minChild + 1 < n && a[minChild + 1] < a[minChild]){minChild++;  }if (a[minChild] < a[parent])  {Swap(&a[minChild], &a[parent]);  parent = minChild;      minChild = parent * 2 + 1;  }else  {break;}}}
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);  //将根部元素与最后一个元素交换，然后再向下调整php->size--;  //相当于删除了最后一个元素AdjustDown(php->a, php->size, 0);
}

删除堆顶元素，首先保证堆有元素，再交换堆顶元素和最后一个元素，size--就相当于删除了最后一个元素，再调用向下调整函数。将数组的地址和数组的元素个数还有数组的首元素下标传给向下调整函数，开始调整。模拟实现的是小堆所以较大的元素在堆的下方，小的元素在较上方，每一个父节点都有两个子节点所以该和谁交换使得根节点的数据往下调整呢？？ 首先根据父节点的数组下标得出左孩子的数组下标，默认最小孩子minChild为左孩子，如果右孩子比左孩子小那就让minChild+1将这个调整最小孩子的动做放到while循环中，因为每一次调整都得和最小孩子交换位置。循环调整的停止条件是minChild小于n因为要保证交换的元素下标是在数组范围内的不能越界交换（这个条件也是循环最多次的条件）。

当a[minChild] < a[parent]时就进行交换调整。当父亲和最小孩子的值相等或者小于最小孩子的值 那就跳出循环 向下调整完成。

打印堆元素（以数组的形式打印）

void PrintHeap(HP* php)
{for (int i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}

判空

bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

取堆顶元素

//返回堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php->a[0];
}

元素个数

int HeapSize(HP* php)
{assert(php);return php->size;
}

销毁

void HeapDestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

2.测试用例：

#include"Heap.h"int main()
{HP hp;HeapInit(&hp);int arr[] = { 65,100,70,32,50,60 };for (int i = 0; i < sizeof(arr) / sizeof(int); i++){HeapPush(&hp, arr[i]);}while (!HeapEmpty(&hp))  //不为空时{printf("%d ", HeapTop(&hp));  //打印堆顶的元素HeapPop(&hp);   //删除堆顶的元素  三行代码就实现了出堆，调整，打印堆顶元素}                    //一直循环直到堆为空时循环停止HeapDestory(&hp);  //销毁堆return 0;
}

3.整体代码：

test.c:

#include"Heap.h"int main()
{HP hp;HeapInit(&hp);int arr[] = { 65,100,70,32,50,60 };for (int i = 0; i < sizeof(arr) / sizeof(int); i++){HeapPush(&hp, arr[i]);}while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapDestory(&hp);return 0;
}

Heap.c:

#include"Heap.h"void HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;}
void HeapDestory(HP* php)
{free(php->a);php->a = NULL;}void PrintHeap(HP* php)
{for (int i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0)  //最坏的情况是孩子一直向上调整 ，最大的范围就是到了数组的第一个位置{if (a[child] < a[parent])    //大小堆在这里调整      插入的元素在最后一个  小堆：<    大堆：   >{Swap(&a[child], &a[parent]);  //交换孩子和父亲的值child = parent;         //再将之前父亲的位置给孩纸，parent = (child - 1) / 2;   //相当于现在是孙子和爷爷位置的比较}else     //当孩子大于等于父亲的值时就不用调整了，可以退出循环{break;}}
}void AdjustDown(HPDataType* a, int n, int parent)//向下调整  数组传过来  数组的大小  根节点的下标
{int minChild = parent * 2 + 1;   //默认最小的孩子是左孩子while (minChild < n){if (minChild + 1 < n && a[minChild + 1] < a[minChild]){minChild++;  //当右孩子比左孩子小 那么最小的孩子就变为右孩子}if (a[minChild] <a[parent])  //当父亲比孩子大时 ，那父亲就要和孩子交换位置{Swap(&a[minChild], &a[parent]);  //调用交换函数  交换值parent = minChild;      //交换完成后父亲还要继续和下边的孩子比较 ，将最小孩子的位置给给父亲minChild = parent * 2 + 1;  //父亲来到了上一个最小孩子的位置，此时这个位置的下一行的最小孩子又默认为左孩子继续比较 }else  //当父亲和最小孩子的值相等或者小于最小孩子的值   那就跳出循环  向下调整完成{break;}}}//插入x  保持堆形态
void HeapPush(HP* php, HPDataType x) //用结构体的指针接收对象的指针   接收 最后一个元素 
{assert(php);if (php->size == php->capacity)  //检查容量{int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(-1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);   //传过去对象的指针  和对象的最后一个元素
}//删除堆顶的元素----为了找到次大的元素
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);  //将根部元素与最后一个元素交换，然后再向下调整php->size--;  //相当于删除了最后一个元素AdjustDown(php->a, php->size, 0);
}//返回堆顶的元素
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php->a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;}int HeapSize(HP* php)
{assert(php);return php->size;
}

Heap.h

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef  int  HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;}HP;void PrintHeap(HP* php);void HeapInit(HP* php);
void HeapDestory(HP* php);//插入数据x 继续保持堆的形态
void HeapPush(HP* php, HPDataType x);//删除堆顶的元素
void HeapPop(HP* php);//返回堆顶的元素
HPDataType HeapTop(HP* php);bool HeapEmpty(HP* php);int HeapSize(HP* php);