什么是堆
在计算机科学中，堆（Heap）是一种特殊的数据结构，它是一种完全二叉树（或者近似完全二叉树），并且满足堆属性。堆有两种常见的类型：最大堆（Max Heap）和最小堆（Min Heap）。最大堆中，父节点的值大于或等于其子节点的值，而最小堆中，父节点的值小于或等于其子节点的值。堆的主要特点是根节点（顶部节点）具有最大（或最小）值。这使得堆在很多应用中非常有用，例如优先队列和堆排序算法。
堆的实现可以使用数组或者链表来表示。在数组实现中，根节点存储在索引位置0，而子节点的索引位置可以通过简单的计算得到。在链表实现中，每个节点包含一个值和指向左右子节点的指针。需要注意的是，堆并不是排序的数据结构，它只保证了根节点的值是最大（或最小）的。如果需要对堆进行排序，可以使用堆排序算法。
堆在计算机科学中有很多应用，以下是一些常见的用途：
-
优先队列：常用于任务调度、事件处理等场景。
-
堆排序：堆排序是一种高效的排序算法。
-
图算法：如Prim算法和Dijkstra算法。
-
堆化数据结构：如哈希表、哈夫曼树、二叉搜索树等。
-
操作系统：在动态内存分配。
-
搜索算法：如A*算法。
向上渗透（入堆）
一般是入堆的操作，如图确定4和5号的数值谁更大，向上进行替换，当小于父节点或者到达根节点时，入堆结束得出结果 。
向下渗透
一般是出堆的操作，如图开始确定2和3号的数值谁更大，向下进行交换，当到达末端节点时，出堆结束得出结果 。
实现代码
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>
typedef int DataType;
typedef struct Heap
{DataType* data;int maxSize;int count;
}Heap;
Heap* create_heap(int maxSize)
{Heap* heap = (Heap*)calloc(1, sizeof(Heap));assert(heap);//heap->data[0] 这个不使用heap->data = (DataType*)calloc(maxSize+1, sizeof(DataType));assert(heap->data);heap->maxSize = maxSize;heap->count = 0;return heap;
}
int size_heap(Heap* heap)
{return heap->count;
}
bool empty_heap(Heap* heap)
{return heap->count == 0;
}
//调整位置
void move(Heap* heap, int curPos)
{while (curPos > 1) {int curData = heap->data[curPos];//父节点的序号=孩子节点序号/2;int parentPos = curPos / 2;if (curData > heap->data[parentPos]) {heap->data[curPos] = heap->data[parentPos];heap->data[parentPos] = curData;curPos = parentPos;}else {//小于父节点的值，位置不需要调整break;}}
}void push_heap(Heap* heap, DataType data) //入堆前置++
{if (heap->count == heap->maxSize) {return;}heap->data[++heap->count] = data; //heap->data[1]=89//向上渗透 move(heap, heap->count);//比较并调整位置
}
int pop_heap(Heap* heap) //出堆
{int max = heap->data[1];//向下渗透int curPos = 1;int childPos = curPos * 2;while (childPos <= heap->count){DataType temp = heap->data[childPos];if (childPos + 1 <= heap->count && temp < heap->data[childPos + 1]){temp = heap->data[++childPos];}heap->data[curPos] = temp;curPos = childPos;childPos *= 2;}heap->data[curPos] = heap->data[heap->count];move(heap, curPos);heap->count--;return max;
}
int main()
{srand((unsigned int)time(NULL));Heap* heap = create_heap(10);for (int i = 0; i < 10; i++){push_heap(heap, rand() % 100);}printf("数组存储结构:\n");for (int i = 1; i <= 10; i++){printf("%d\t", heap->data[i]);}printf("\n");printf("堆排序:\n");while (!empty_heap(heap)) {printf("%d\t", pop_heap(heap));}return 0;
}
