【数据结构】堆(一)
😛作者:日出等日落
📘 专栏:数据结构
如果我每天都找出所犯错误和坏习惯,那么我身上最糟糕的缺点就会慢慢减少。这种自省后的睡眠将是多么惬意啊。
目录
🎄堆的概念及结构:
🎄堆的实现:
✔基本接口函数:
✔结构体:
✔HeapInit函数:
✔HeapDestory函数:
✔HeapPrint函数:
✔HeapPush函数:
✔HeapPop函数:
✔HeapTop函数:
🎄完整代码:
✔Heap.h:
✔Heap.c:
✔Text.c:
🎄堆的概念及结构:
如果有一个关键码的集合K = { k0,k1 ,k2 ,…,k(n-1) },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:Ki <= K(2*i+1)且 Ki <= K(2*i+2) (Ki >= K(2*i+1)且Ki >= K(2*i+2)) i = 0,1, 2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
堆的性质:
- 堆中某个节点的值总是不大于或不小于其父节点的值
- 堆总是一棵完全二叉树
- 简单来说:
- 父节点都比其的子节点大的完全二叉树叫做大堆。
- 父节点都比其的子节点小的完全二叉树叫做小堆。
如图:
🎄堆的实现:
✔基本接口函数:
//堆的初始化
void HeapInit(HP* hph);//堆的销毁
void HeapDestory(HP* hph);//堆的打印
void HeapPrint(HP* hph);// 堆的插入
void HeapPush(HP * hph, HPDataType x);// 堆的删除
void HeapPop(HP* hph);// 取堆顶的数据
HPDataType HeapTop(HP* hph);// 堆的数据个数
int HeapSize(HP* hph);// 堆的判空
int HeapEmpty(HP* hph);
✔结构体:
typedef int HPDataType;
typedef struct heap
{HPDataType* a;int capacity;int size;
}HP;
✔HeapInit函数:
//堆的初始化
void HeapInit(HP* hph)
{assert(hph);hph->a = NULL;hph->capacity = hph->size = 0;
}
✔HeapDestory函数:
//堆的销毁
void HeapDestory(HP* hph)
{assert(hph);free(hph->a);hph->a = NULL;hph->capacity = 0;hph->size = 0;
}
✔HeapPrint函数:
//堆的打印
void HeapPrint(HP* hph)
{for (int i = 0; i < hph->size; ++i){printf("%d ", hph->a[i]);}printf("\\n");
}
✔HeapPush函数:
当capacity==size时扩容(包括初始化的方案),当size==0时,扩容4个空间,否则扩容二倍的空间,capacity也跟着扩大,当push后size++。
Swap交换函数:
void Swap(HPDataType* p1, HPDataType* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//向上调整
//child和parent都是下标
void AdjusUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child>0){if (a[parent] < a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}// 堆的插入
void HeapPush(HP* hph, HPDataType x)
{assert(hph);//扩容if (hph->capacity == hph->size){int newcapacity = hph->capacity == 0 ? 4 : hph->capacity * 2;HPDataType* tmp = (HPDataType* )realloc(hph->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail:");exit(-1);}hph->a = tmp;hph->capacity = newcapacity;}hph->a[hph->size] = x;hph->size++;//向上调整AdjusUp(hph->a, hph->size - 1);
}
✔HeapPop函数:
出堆顶的元素,让第一个位置的值和最后一个位置的值交换,再size--就相当于删除了,但交换上去的值在根节点的位置上,我们无法维持是大堆的情况,因此还需要向下调整Ajustdown。
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1< n && a[child] < a[child + 1]){child = child + 1;}//child 大于 parent 就交换if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 堆的删除
void HeapPop(HP* hph)
{assert(hph);assert(!HeapEmpty(hph));Swap(&hph->a[0], &hph->a[hph->size - 1]);hph->size--;AdjustDown(hph->a, hph->size, 0);
}
✔HeapTop函数:
// 取堆顶的数据
HPDataType HeapTop(HP* hph)
{assert(hph);assert(hph->size > 0);return hph->a[0];
}
🎄完整代码:
✔Heap.h:
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>typedef int HPDataType;
typedef struct heap
{HPDataType* a;int capacity;int size;
}HP;//堆的初始化
void HeapInit(HP* hph);//堆的销毁
void HeapDestory(HP* hph);//堆的打印
void HeapPrint(HP* hph);// 堆的插入
void HeapPush(HP * hph, HPDataType x);// 堆的删除
void HeapPop(HP* hph);// 取堆顶的数据
HPDataType HeapTop(HP* hph);// 堆的数据个数
int HeapSize(HP* hph);// 堆的判空
int HeapEmpty(HP* hph);
✔Heap.c:
#define _CRT_SECURE_NO_WARNINGS 1
#include "heap.h"//堆的打印
void HeapPrint(HP* hph)
{for (int i = 0; i < hph->size; ++i){printf("%d ", hph->a[i]);}printf("\\n");
}//堆的初始化
void HeapInit(HP* hph)
{assert(hph);hph->a = NULL;hph->capacity = hph->size = 0;
}//堆的销毁
void HeapDestory(HP* hph)
{assert(hph);free(hph->a);hph->a = NULL;hph->capacity = 0;hph->size = 0;
}
void Swap(HPDataType* p1, HPDataType* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整
//child和parent都是下标
void AdjusUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child>0){if (a[parent] < a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}// 堆的插入
void HeapPush(HP* hph, HPDataType x)
{assert(hph);//扩容if (hph->capacity == hph->size){int newcapacity = hph->capacity == 0 ? 4 : hph->capacity * 2;HPDataType* tmp = (HPDataType* )realloc(hph->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail:");exit(-1);}hph->a = tmp;hph->capacity = newcapacity;}hph->a[hph->size] = x;hph->size++;//向下调整AdjusUp(hph->a, hph->size - 1);
}//向上调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1< n && a[child] < a[child + 1]){child = child + 1;}//child 大于 parent 就交换if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 堆的删除
void HeapPop(HP* hph)
{assert(hph);assert(!HeapEmpty(hph));Swap(&hph->a[0], &hph->a[hph->size - 1]);hph->size--;AdjustDown(hph->a, hph->size, 0);
}// 取堆顶的数据
HPDataType HeapTop(HP* hph)
{assert(hph);assert(hph->size > 0);return hph->a[0];
}// 堆的数据个数
int HeapSize(HP* hph)
{assert(hph);return hph->size;
}// 堆的判空
int HeapEmpty(HP* hph)
{assert(hph);return hph->size == 0;
}
✔Text.c:
#define _CRT_SECURE_NO_WARNINGS 1#include "heap.h"void Heap()
{int arry[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };HP hph;HeapInit(&hph);HeapPrint(&hph);for (int i = 0; i < sizeof(arry) / sizeof(int); i++){HeapPush(&hph, arry[i]);}HeapPrint(&hph);HeapPush(&hph, 100);HeapPrint(&hph);HeapPop(&hph);HeapPrint(&hph);HeapDestory(&hph);
}
void TestHeap2()
{int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };HP hp;HeapInit(&hp);for (int i = 0; i < sizeof(array) / sizeof(int); ++i){HeapPush(&hp, array[i]);}while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}HeapDestroy(&hp);
}int main()
{TestHeap2();return 0;
}