[数据结构]堆

堆，本质是一颗完全二叉树。属于非线性结构。

代码实现可参考树的代码。

函数介绍:

//此堆是小堆,大堆操作部分与小堆相反
void InitHeap(Heap* cat)
{assert(cat);cat->arr = NULL;cat->capacity = cat->size = 0;
}
void DestroyHeap(Heap* cat)
{assert(cat);if (cat->arr)free(cat->arr);cat->arr = NULL;
}
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
void AdjustUp(Type* arr, int child)//小堆
{int parent = (child - 1) / 2;while (child > 0){if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
void HeapPush(Heap* cat, Type x)
{assert(cat);if (cat->capacity == cat->size){int newcapacity = cat->capacity == 0 ? 4 : 2 * cat->capacity;Type* tmp = (Type*)realloc(cat->arr, newcapacity * sizeof(Type));if (tmp == NULL){perror("realloc fail!");exit(1);}cat->capacity = newcapacity;cat->arr = tmp;}cat->arr[cat->size++] = x;AdjutUp(cat->arr, cat->size);
}
void AdjustDown(Type* arr, int parent, int n)//小堆
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && arr[child] > arr[child + 1])//找{child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapPop(Heap* cat)
{assert(cat);Swap(&cat->arr[0], &cat->arr[cat->size - 1]);--cat->size;AdjustDown(cat->arr, 0, cat->size - 1);
}
//判空
bool HeapEmpty(Heap* cat)
{assert(cat);return cat->size == 0;
}
//输出堆顶数据
Type HeapTop(Heap* cat)
{assert(cat);return cat->arr[0];
}
//打印堆可用三种遍历方式打印或者树的层序遍历，此处省略

头文件介绍：

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int Type;
typedef struct Heap {Type* arr;int capacity;int size;
}Heap;
void InitHeap(Heap* cat);
void DestroyHeap(Heap* cat);
void Swap(int* x, int* y);
void AdjustUp(Type* arr, int child);
void HeapPush(Heap* cat, Type x);
void AdjustDown(Type* arr, int parent, int n);
void HeapPop(Heap* cat);
bool HeapEmpty(Heap* cat);
Type HeapTop(Heap* cat);

谢谢观看!