目录
2.堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
1.堆的定义:
只要满足以下两个条件,就是堆(Heap):
1.堆是完全二叉树;
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
2.堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
小堆:任何一个父亲<=孩子
大堆:任何一个父亲>=孩子
2.堆的代码实现: (小堆)
存储结构:
typedef int HeapDataType;
typedef struct Heap {
HeapDataType* hp;
int size;
int capacity;
}Heap;
初始化(HeapInit):
- 功能:为堆分配内存空间,并设置初始容量为
n
。 - 细节:使用
malloc
为堆的数据元素分配内存,并设置堆的大小为0,容量为n
。 void HeapInit(Heap*heap,int n) { assert(heap); HeapDataType* hp = (HeapDataType*)malloc(n * sizeof(HeapDataType)); if (hp == NULL) { perror("HeapInit:malloc"); exit(1); } heap->hp = hp; heap->capacity = n; heap->size = 0; }
- 功能:为堆分配内存空间,并设置初始容量为
插入(HeapPush):
- 功能:向堆中插入一个元素。
- 细节:首先检查堆是否已满,如果已满则尝试扩大堆的容量。然后将新元素添加到堆的末尾,并通过
adjustup
函数调整堆的结构以保持小堆的性质(即父节点值不大于孩子节点值)。 void HeapPush(Heap* heap,HeapDataType x) { assert(heap); if (HeapFull(heap)) { int new = heap->capacity == 0 ? 4 : 2 * heap->capacity; HeapDataType* tmp = (HeapDataType*)realloc(heap->hp, new * sizeof(HeapDataType)); if (tmp == NULL) { perror("HeapPush:realloc"); exit(1); } heap->hp = tmp; heap->capacity = new; } heap->hp[heap->size] = x; adjustup(heap->hp, heap->size); heap->size++; }
删除堆顶元素(HeapPop):
- 功能:删除堆顶元素(即最小元素),并重新调整堆的结构。
- 细节:首先检查堆是否为空。然后将堆的最后一个元素移到堆顶,并通过
adjustdown
函数重新调整堆以保持小堆性质。堆的大小减1。 void HeapPop(Heap* heap) { assert(heap); if (HeapEmpty(heap)) { perror("HeapPop:NULL"); exit(1); } HeapDataType x = heap->hp[0]; heap->hp[0] = heap->hp[heap->size - 1]; heap->hp[heap->size - 1] = x; heap->size--; adjustdown(heap->hp, 0, heap->size); }
查看堆顶元素(HeapPeek):
- 功能:返回堆顶元素的值,但不删除它。
- 细节:直接返回堆顶元素的值。这通常用于查看当前最小元素的值,而不改变堆的结构。
HeapDataType HeapPeek(Heap*heap) { assert(heap); if (HeapEmpty(heap)) { perror("HeapPeek:NULL"); exit(1); } return heap->hp[0]; }
检查堆满(HeapFull)和堆空(HeapEmpty):
- 功能:检查堆是否已满或是否为空。
- 细节:
HeapFull
检查堆的大小是否等于其容量,而HeapEmpty
检查堆的大小是否为0。 bool HeapFull(Heap*heap) { return heap->capacity == heap->size; }
bool HeapEmpty(Heap* heap) { return heap->size == 0; }
销毁堆(HeapDestroy):
- 功能:释放堆所占用的内存空间。
- 细节:使用
free
函数释放堆的数据元素所占用的内存,并将堆的指针、容量和大小都重置为0。 void HeapDestory(Heap*heap) { assert(heap&&heap->hp); free(heap->hp); heap->hp = NULL; heap->capacity = 0; heap->size = 0; }
堆化(Heapify):
- 功能:将一个数组重新调整为小堆结构。
- 细节:通常用于在堆构建完成后或在执行某些操作(如删除元素)后重新调整堆的结构。从最后一个非叶子节点开始,自底向上调整每个节点,以保持小堆的性质。
void Heapify(HeapDataType*a,int n) { assert(a); int i = (n - 1 - 1) / 2 ; for (i; i >= 0; i--) { adjustdown(a, i, n); } }
上滤(adjustup)和下滤(adjustdown):
- 功能:这两个函数用于在插入或删除元素后调整堆的结构。
- 细节:
adjustup
用于在插入新元素后,从插入位置开始向上调整堆结构;adjustdown
用于在删除堆顶元素后,从堆顶开始向下调整堆结构。这两个函数都通过比较节点与其子节点的值,并交换它们(如果需要)来保持小堆的性质。 void adjustup(HeapDataType*hp,int i) { assert(hp); int j = (i - 1) / 2; while (j>=0) { if (hp[i] < hp[j]) { HeapDataType x = hp[i]; hp[i] = hp[j]; hp[j] = x; i = j; j = (i - 1) / 2; } else { break; } } }
void adjustdown(HeapDataType* hp, int i, int n) { assert(hp&&i<n); int j = 2 * i + 1; if (hp[j] > hp[j + 1]&&j<n-1) { j++; } if (hp[j] < hp[i]&&j<n) { HeapDataType x = hp[i]; hp[i] = hp[j]; hp[j] = x; adjustdown(hp, j, n); } }
3.完整代码:
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HeapDataType;
typedef struct Heap {
HeapDataType* hp;
int size;
int capacity;
}Heap;
//小堆
void adjustup(HeapDataType*hp,int i) {
assert(hp);
int j = (i - 1) / 2;
while (j>=0) {
if (hp[i] < hp[j]) {
HeapDataType x = hp[i];
hp[i] = hp[j];
hp[j] = x;
i = j;
j = (i - 1) / 2;
}
else {
break;
}
}
}
void adjustdown(HeapDataType* hp, int i, int n) {
assert(hp&&i<n);
int j = 2 * i + 1;
if (hp[j] > hp[j + 1]&&j<n-1) {
j++;
}
if (hp[j] < hp[i]&&j<n) {
HeapDataType x = hp[i];
hp[i] = hp[j];
hp[j] = x;
adjustdown(hp, j, n);
}
}
void HeapInit(Heap*heap,int n) {
assert(heap);
HeapDataType* hp = (HeapDataType*)malloc(n * sizeof(HeapDataType));
if (hp == NULL) {
perror("HeapInit:malloc");
exit(1);
}
heap->hp = hp;
heap->capacity = n;
heap->size = 0;
}
void Heapify(HeapDataType*a,int n) {
assert(a);
int i = (n - 1 - 1) / 2 ;
for (i; i >= 0; i--) {
adjustdown(a, i, n);
}
}
void HeapDestory(Heap*heap) {
assert(heap&&heap->hp);
free(heap->hp);
heap->hp = NULL;
heap->capacity = 0;
heap->size = 0;
}
bool HeapFull(Heap*heap) {
return heap->capacity == heap->size;
}
bool HeapEmpty(Heap* heap) {
return heap->size == 0;
}
void HeapPush(Heap* heap,HeapDataType x) {
assert(heap);
if (HeapFull(heap)) {
int new = heap->capacity == 0 ? 4 : 2 * heap->capacity;
HeapDataType* tmp = (HeapDataType*)realloc(heap->hp, new * sizeof(HeapDataType));
if (tmp == NULL) {
perror("HeapPush:realloc");
exit(1);
}
heap->hp = tmp;
heap->capacity = new;
}
heap->hp[heap->size] = x;
adjustup(heap->hp, heap->size);
heap->size++;
}
void HeapPop(Heap* heap) {
assert(heap);
if (HeapEmpty(heap)) {
perror("HeapPop:NULL");
exit(1);
}
HeapDataType x = heap->hp[0];
heap->hp[0] = heap->hp[heap->size - 1];
heap->hp[heap->size - 1] = x;
heap->size--;
adjustdown(heap->hp, 0, heap->size);
}
HeapDataType HeapPeek(Heap*heap) {
assert(heap);
if (HeapEmpty(heap)) {
perror("HeapPeek:NULL");
exit(1);
}
return heap->hp[0];
}
int main()
{
Heap* heap = (Heap*)malloc(sizeof(Heap));
HeapInit(heap, 5);
HeapPush(heap, 4);
HeapPush(heap, 2);
HeapPush(heap, 15);
HeapPush(heap, 7);
HeapPush(heap, 9);
for (int i = 0; i < 5; i++) {
printf("%d ", heap->hp[i]);
}
HeapDestory(heap);
return 0;
}