个人主页 ： 个人主页
个人专栏 ： 《数据结构》 《C语言》
文章目录
- 一、堆
- 二、实现思路
- 1. 结构的定义
- 2. 堆的构建 (HeapInit)
- 3. 堆的销毁 (HeapDestroy)
- 4. 堆的插入 (HeapPush)
- 5. 堆的删除 (HeapPop)
- 6. 取堆顶的数据 (HeapTop)
- 7. 堆的数据个数 (HeapSize)
- 8. 堆的判空 (HeapEmpty)
- 三、代码实现
- 总结
一、堆
当一颗完全二叉树用顺序表来存储时，其被称为堆。
- 堆总是一棵完全二叉树
- 堆的某个节点的值总是不大于(大堆)或不小于(小堆)其父节点的值
其可以被用来解决top k 问题 或 堆排序
下面就是要实现的堆的功能 重点在于堆的插入 和 堆的删除
//堆的构建void HeapInit(Heap* hp);//堆的销毁void HeapDestroy(Heap* hp);//堆的插入void HeapPush(Heap* hp, HPDataType x);//堆的删除void HeapPop(Heap* hp);//取堆顶的数据HPDataType HeapTop(Heap* hp);//堆的数据个数int HeapSize(Heap* hp);//堆的判空bool HeapEmpty(Heap* hp);二、实现思路
下部分的图，都以逻辑结构为主！！！
这里构建的是小堆。
1. 结构的定义
堆就是用顺序表来存储一颗完全二叉树，那么堆的结构就与顺序表的结构相同。
一个指向动态开辟空间的指针(data)，一个变量记录空间大小(capacity)，一个变量记录空间中有效数据(size)。
typedef int HPDataType;typedef struct Heap{HPDataType* data;int capacity;int size;}Heap;2. 堆的构建 (HeapInit)
malloc一块空间，用data记录其地址，capacity记录此时空间大小，size置0(此时空间内无有效数据)。
//堆的构建#define SIZE 4void HeapInit(Heap* hp){assert(hp);hp->data = (HPDataType*)malloc(sizeof(HPDataType) * SIZE);if (hp == NULL) {perror("mallo: ");exit(-1);}hp->capacity = SIZE;hp->size = 0;}3. 堆的销毁 (HeapDestroy)
free掉动态开辟的空间，使capacity 和 size 置 0(此时空间大小为0)
//堆的销毁void HeapDestroy(Heap* hp){assert(hp);free(hp->data);hp->data = NULL;hp->capacity = hp->size = 0;}4. 堆的插入 (HeapPush)
将数据插入到堆的尾部(最后一个子节点后)，然后与其父节点相比较，如果该节点小于其父节点(这里是小堆)，交换两个节点的值，直到该节点为堆顶或其父节点小于该节点。
- 假设该节点下标是 i，那么其父节点的小标是 ( i – 1 ) / 2
//交换void swap(HPDataType* a, HPDataType* b){HPDataType tmp = *a;*a = *b;*b = tmp;}//向上调整 假设该节点是 i，父节点是 (i - 1) / 2void AdjustUp(HPDataType* data, int child){int parent = (child - 1) / 2;while (child > 0){if (data[child] < data[parent]){swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}}//堆的插入void HeapPush(Heap* hp, HPDataType x){assert(hp);//检查容量if (hp->capacity == hp->size){HPDataType* tmp = (HPDataType*)realloc(hp->data ,sizeof(HPDataType) * (hp->capacity * 2));if (tmp == NULL){perror("realloc:");exit(-1);}hp->data = tmp;hp->capacity *= 2;}hp->data[hp->size] = x;hp->size++;//向上调整 传入数组和出入数据的下标//此处是小堆AdjustUp(hp->data, hp->size - 1);}5. 堆的删除 (HeapPop)
堆的删除是删除堆顶数据。
堆顶数据和堆的尾部数据交换，size 减一，然后将新的堆顶数据与其左右孩子节点的最小值比较，如果新堆顶数据大于左右孩子节点的最小值，交换数据，再次与新的左右孩子节点的最小值
比较。直到该数据小于左右孩子的最小值，或该数据超出有效数据范围。
- 假设某个节点的下标是 i，其左孩子节点的下标：i * 2 + 1，其右孩子的下标：i * 2 + 2
- 删除堆顶数据，不能挪到数据将堆顶数据覆盖。如果挪到数据，那么兄弟节点可能会变成父子节点，而兄弟节点之间并不保证大小关系，可能会破坏堆的结构(这里是会破坏小堆结构)。
//交换void swap(HPDataType* a, HPDataType* b){HPDataType tmp = *a;*a = *b;*b = tmp;}//向下调整，假设该节点是 i， 右孩子节点是 2 * i + 1，左孩子节点是 2 * i + 2void AdjustDown(HPDataType* data, int parent, int size){int child = parent * 2 + 1;while (parent < size){//防止越界找左右孩子中最小的if (child + 1 < size && data[child] > data[child + 1]){child++;}if (child < size && data[parent] > data[child]){swap(&data[parent], &data[child]);parent = child;child = parent * 2 + 1;}else{break;}}}//堆的删除首元素 与 尾元素交换，新的堆顶在向下调整void HeapPop(Heap* hp){assert(hp);assert(!HeapEmpty(hp));hp->data[0] = hp->data[hp->size - 1];hp->size--;//向下调整AdjustDown(hp->data, 0, hp->size);}6. 取堆顶的数据 (HeapTop)
读取数组空间下标为0处即可。
//取堆顶的数据HPDataType HeapTop(Heap* hp){assert(hp);return hp->data[0];}7. 堆的数据个数 (HeapSize)
堆的结构中size表示此时堆中有效数据的个数，访问size即可。
//堆的数据个数int HeapSize(Heap* hp){assert(hp);return hp->size;}8. 堆的判空 (HeapEmpty)
size表示堆的有效数据个数，如果size == 0，表示堆为空。
//堆的判空bool HeapEmpty(Heap* hp){assert(hp);return hp->size == 0;}三、代码实现
//Heap.c 文件#include "Heap.h"//堆的构建void HeapInit(Heap* hp){assert(hp);hp->data = (HPDataType*)malloc(sizeof(HPDataType) * SIZE);if (hp == NULL) {perror("mallo: ");exit(-1);}hp->capacity = SIZE;hp->size = 0;}//堆的销毁void HeapDestroy(Heap* hp){assert(hp);free(hp->data);hp->data = NULL;hp->capacity = hp->size = 0;}//交换void swap(HPDataType* a, HPDataType* b){HPDataType tmp = *a;*a = *b;*b = tmp;}//向上调整 假设该节点是 i，父节点是 (i - 1) / 2void AdjustUp(HPDataType* data, int child){int parent = (child - 1) / 2;while (child > 0){if (data[child] < data[parent]){swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}//堆的插入void HeapPush(Heap* hp, HPDataType x){assert(hp);//检查容量if (hp->capacity == hp->size){HPDataType* tmp = (HPDataType*)realloc(hp->data ,sizeof(HPDataType) * (hp->capacity * 2));if (tmp == NULL){perror("realloc:");exit(-1);}hp->data = tmp;hp->capacity *= 2;}hp->data[hp->size] = x;hp->size++;//向上调整 传入数组和出入数据的下标//此处是小堆AdjustUp(hp->data, hp->size - 1);}//向下调整，假设该节点是 i， 右孩子节点是 2 * i + 1，左孩子节点是 2 * i + 2void AdjustDown(HPDataType* data, int parent, int size){int child = parent * 2 + 1;while (parent < size){//防止越界找左右孩子中最小的if (child + 1 < size && data[child] > data[child + 1]){child++;}if (child < size && data[parent] > data[child]){swap(&data[parent], &data[child]);parent = child;child = parent * 2 + 1;}else{break;}}}//堆的删除首元素 与 尾元素交换，新的堆顶在向下调整void HeapPop(Heap* hp){assert(hp);assert(!HeapEmpty(hp));hp->data[0] = hp->data[hp->size - 1];hp->size--;//向下调整AdjustDown(hp->data, 0, hp->size);}//取堆顶的数据HPDataType HeapTop(Heap* hp){assert(hp);return hp->data[0];}//堆的数据个数int HeapSize(Heap* hp){assert(hp);return hp->size;}//堆的判空bool HeapEmpty(Heap* hp){assert(hp);return hp->size == 0;}//Heap.h文件#pragma once#include #include #include #include #define SIZE 4typedef int HPDataType;typedef struct Heap{HPDataType* data;int capacity;int size;}Heap;//堆的构建void HeapInit(Heap* hp);//堆的销毁void HeapDestroy(Heap* hp);//堆的插入void HeapPush(Heap* hp, HPDataType x);//堆的删除void HeapPop(Heap* hp);//取堆顶的数据HPDataType HeapTop(Heap* hp);//堆的数据个数int HeapSize(Heap* hp);//堆的判空bool HeapEmpty(Heap* hp);总结
以上就是我对于堆的实现！！！
