数据结构-堆
程序员文章站
2024-02-14 09:45:28
...
堆的性质:
堆是按照完全二叉树的顺序存储方式存储在一个一维数组中。
堆分为小堆和大堆,不满足小堆和大堆性质的二叉树不能叫堆。
小堆:父节点的value < 任何一个子节点的value。(Ki <= K2 * i + 1)且(Ki <= K2 * i + 2);
大堆:父节点的value > 任何一个子节点的value。(Ki >= K2 * i + 1)且(Ki >= K2 * i + 2);
堆的操作:
- 初始化堆
- 创建堆
- 向堆中插入元素
- 打印堆的元素
- 获取堆顶元素
- 删除堆顶元素
- 判断是不是空堆
- 交换两个元素
- 小项堆的向下调整
- 堆排序
- 数据查找(从很多个数里面查找最大或者最小的K个数)
堆数据结构的定义(其实就是顺序表):
#define INIT_HEAP_SIZE 20
typedef int HeapDataType;
typedef struct Heap {
HeapDataType* array;
unsigned int capacity;
unsigned int size;
}Heap;
Compare函数指针定义:
typedef int(*Compare)(int x, int y);
初始化堆
用于给堆中的元素开辟内存,以及初始化开辟内存
void initHeap(Heap* heap) {
if (heap == NULL)
return;
heap->array = (HeapDataType*)malloc(sizeof(HeapDataType)*INIT_HEAP_SIZE);
heap->capacity = INIT_HEAP_SIZE;
heap->size = 0;
for (int i = 0; i < heap->capacity; i++) {
heap->array[i] = 0;
}
}
创建堆
步骤:
- 找到临界点
- 从临界点开始向下调整(
- 找最小的左右孩子,
- 如果当前节点比最小孩子大,
- 则交换当前节点和最小孩子,
- 循环这个步骤,直到不满足条件
)
- 临界点自减1;继续以上步骤
/**
创建小根堆(向上调整)
*/
void createHeap(Heap* heap, HeapDataType* arr, unsigned int len, Compare com) {
if (heap == NULL)
return;
for (int i = 0; i < len; i++) {
heap->array[i] = arr[i];
heap->size++;
}
// 找到零界点
int flag = (len - 1) / 2;
flag--;
while (flag >= 0) {
int parrent = flag;
while (1) {
int child = parrent * 2 + 1;
if (child >= len)
break;
if (child + 1 >= len) {
if (com(heap->array[child], heap->array[parrent])) {
swap(&heap->array[child], &heap->array[parrent]);
parrent = child;
break;
}
else {
break;
}
}
// 找最大/小的左右孩子
if (!com(heap->array[child], heap->array[child + 1])) {
child++;
}
// 将当前节点和最大/小的孩子比较,如果比最大/小的孩子小/大则交换。
if (com(heap->array[child], heap->array[parrent])) {
swap(&heap->array[child], &heap->array[parrent]);
parrent = child;
}
else {
break;
}
}
flag--;
}
}
向堆中插入元素
步骤:
- 将元素放到堆尾(数组的最后)
- 将该元素向上调整
// 向堆中插入元素(向上调整)
void insertIntoHeap(Heap* heap, HeapDataType insertData, Compare com) {
// 将元素放入堆尾
heap->size++;
heap->array[heap->size - 1] = insertData;
if (heap->size == 1)
return;
int child = heap->size - 1;
while (1) {
int parrent = (child - 1) / 2;
//如果当前元素比父元素小,就向上移动
if (com(heap->array[child], heap->array[parrent])) {
swap(&(heap->array[child]), &(heap->array[parrent]));
child = parrent;
if (parrent == 0)
break;
}
else {
break;
}
}
}
打印堆的元素
// 打印数组元素
void printHeap(Heap* heap) {
int sum = 1;
int j = 0;
for (int i = 0; i < heap->size; i++) {
if (i == sum - 1)
for (int j = 0; j < heap->size - i; j++) {
printf(" ");
}
else
printf(" ");
printf("%d", heap->array[i]);
j++;
if (sum == j) {
printf("\n");
sum *= 2;
j = 0;
}
else if (i == 0)
printf("\n");
}
printf("\n");
}
获取堆顶元素
获取数组的第0个元素
HeapDataType getHeapTop(Heap* heap) {
if (!isEmptyHeap)
return heap->array[0];
return -1;
}
删除堆顶元素
步骤:
- 将最后一个元素赋值给第一个元素。
- 删除最后一个元素
- 对堆顶元素进行向下调整
// 删除堆顶元素
void deleteFromHeap(Heap* heap, Compare com) {
if (heap == NULL)
return;
if (isEmptyHeap(heap))
return;
heap->size--;
// 将最后一个元素赋值给第一个元素
heap->array[0] = heap->array[heap->size];
// 将根元素赋值给parrent
int parrent = 0;
// 向下调整
while (1) {
int child = parrent * 2 + 1;
if (child >= heap->size)
break;
if (child + 1 >= heap->size) {
if (com(heap->array[child], heap->array[parrent])) {
swap(&heap->array[parrent], &heap->array[child]);
parrent = child;
}
else {
break;
}
}
if (!com(heap->array[child], heap->array[child + 1])) {
child++;
}
if (com(heap->array[child], heap->array[parrent])) {
swap(&heap->array[parrent], &heap->array[child]);
parrent = child;
}
else {
break;
}
}
}
判断是不是空堆
int isEmptyHeap(Heap* heap) {
return heap->size == 0 ? 1 : 0;
}
交换两个元素
void swap(HeapDataType* data1, HeapDataType* data2) {
HeapDataType tmp = *data1;
*data1 = *data2;
*data2 = tmp;
}
小根堆的向下调整
由于调整的左右子树已经是一个堆了,只需要对堆顶元素进行向下调整即可
// 小根堆的向下调整
void topDownHeap(Heap* heap, int size, Compare com) {
if (size == 0)
return;
int parrent = 0;
int child = 0;
while (1) {
child = parrent * 2 + 1;
if (child > size)
break;
if (child + 1 > size) {
if(com(heap->array[child], heap->array[parrent]))
swap(&heap->array[parrent], &heap->array[child]);
break;
}
// 找到两个孩子之间比较大的
if (!com(heap->array[child], heap->array[child + 1])) {
child++;
}
// 父节点和最大的孩子比较,小于最大孩子,则交换
if (com(heap->array[child], heap->array[parrent])) {
swap(&heap->array[parrent], &heap->array[child]);
parrent = child;
}
else {
break;
}
}
}
堆排序
- 将堆顶元素和最后一个元素(下标为n)交换;
- n--;
- 对前n - 1个元素进项向下调整(堆顶的向下调整)
- 继续1,直到n == 0
// 堆排序,从大到小
void heapSort(Heap* heap, Compare com) {
int end = heap->size - 1;
while (end > 0) {
swap(&heap->array[0], &heap->array[end]);
--end;
// 调整
topDownHeap(heap, end, com);
}
}
数据查找(从很多个数里面查找最大的K个数)
步骤
- 将堆的前K个数插入小项堆中
- 插入后n - k个数据,每次都比较准备插入的数据和堆顶的大小。如果大于堆顶,则替换堆顶,并对堆顶进行向下调整。
// 数据查找(从很多个数里面查找最大或者最小的K个数)
void getDataFromGreatData(HeapDataType* arr, unsigned int len, unsigned int k, Compare com) {
Heap* heap = (Heap*)malloc(sizeof(Heap));
if (heap == NULL || k == 0 || len <= k)
return;
initHeap(heap);
if (len <= k) {
// 将前len个数插入堆中
createHeap(heap, arr, len, com);
return;
}
// 将前K个数插入堆中
createHeap(heap, arr, k, com);
for (int i = k; i < len; i++) {
// 获取堆顶元素
HeapDataType top = getHeapTop(heap);
if (top < arr[i]) {
deleteFromHeap(heap, com);
insertIntoHeap(heap, arr[i], com);
}
}
printHeap(heap);
}
测试用例:
int main() {
Heap* heap = (Heap*)malloc(sizeof(Heap));
if (heap == NULL)
return 0;
initHeap(heap);
HeapDataType arr[] = {53, 17, 78, 9, 45, 65, 87, 23, 31};
createHeap(heap, arr, sizeof(arr)/sizeof(arr[0]), Greater);
insertIntoHeap(heap, 5, Greater);
insertIntoHeap(heap, 50, Greater);
insertIntoHeap(heap, 13, Greater);
deleteFromHeap(heap, Greater);
printf("构建堆\n");
printHeap(heap);
printf("\n获取堆中5个最大/小的元素\n");
getDataFromGreatData(heap->array, heap->size, 5, Greater);
printf("\n堆排序\n");
heapSort(heap, Greater);
printHeap(heap);
printf("\n");
return 0;
}
运行截图:
小根堆
大根堆:
完整代码在Git:github.com/Niceug