堆是以二叉树为结构组成的一个序列，一般以数组进行实现，如设 N = 1 为根节点，则左节点 2*N，右节点 2*N+1，以此构建一整个堆。
堆结构体的数据结构
typedef int Item;
typedef struct maxHeap {
Item* data; // 堆的数组实现
int count; // 实际存在的数据量
} maxHeap, *pmaxHeap;
初始化
void init(pmaxHeap heap, int capacity) {
heap->data = (Item*)malloc(sizeof(Item) * capacity);
heap->count = 0;
}
堆内存中为结构体的data数组开辟内存空间
初始化结构体属性count=0
返回堆数组的数据量
int size(pmaxHeap heap) { return heap->count; }
判断堆数组是否为空
bool isEmpty(pmaxHeap heap) { return heap->count == 0; }
交换函数(数组的交换)
void swap(Item* item, int i, int j) {
Item temp = *(item + i);
*(item + i) = *(item + j);
*(item + j) = temp;
}
堆数组最重要的便是插入新数据和返回堆顶的那个值，与之相对应的就是插入新数据的时候的shiftUp，和返回堆顶元素后的shiftDown。为了调节堆数组结构保持最大堆或最小堆的结构。
插入函数和shiftUp函数
// 插入新元素
void insert(pmaxHeap heap, Item item) {
heap->data[++(heap->count)] = item;
shiftUp(heap, heap->count);
}
插入新元素后，堆数组的count要++，且插入的新元素位置就是++后的位置，因此直接++count。（另一层含义就是以下标为1的位置作为根节点。）
shiftUp进行插入新元素的排位。
void shiftUp(pmaxHeap heap, int k) {
while (k > 1 && heap->data[k / 2] < heap->data[k]) {
swap(heap->data, k / 2, k);
k /= 2;
}
}
shiftUp，k暂时表示新插入的元素的位置，使之和 k/2的元素也就是父节点的元素进行比较，如果父节点比他小（大堆），则交换，并进行下一步 令 k = k/2;
递归的shiftUp
void shiftUp(pmaxHeap heap,int k){
if(k == 1 || heap->data[k/2] > heap->data[k])
return;
swap(heap,k,k/2);
shiftUp(heap,k/2);
}
取出堆顶元素和shiftDown函数
最大堆的堆顶元素就是最大值，取出堆顶元素后，进行shiftDown操作，令最后一个元素移动到堆顶，然后对堆顶进行shiftDown，也就是让其的左节点和右节点相比谁更大，最大的如果比根节点大，那就交换，否则就不交换，然后不断向下，直到 k > heap->count/2。
// 取出堆顶元素（最大值）
Item getHeapMax(pmaxHeap heap) {
if (heap->count == 1) {
heap->count--;
return heap->data[1];
}
int i = 1;
Item item = heap->data[i];
heap->data[i] = heap->data[heap->count--];
shiftDown(heap, i);
return item;
}
如果堆只剩下一个元素，则count--，然后直接返回该元素。
如果不是，则取出堆顶元素，然后将最后一个元素放到堆顶，count记得--。
shiftDown函数，从上往下进行比较交换。
void shiftDown(pmaxHeap heap, int k) {
只要k<=heap->count/2，因为heap->count/2 就到了数组的末尾。
while (k <= heap->count / 2) {
int j = 2 * k;
找到父节点，要和哪个子节点进行交换（如果子节点大于父节点的话）
if (heap->data[j] < heap->data[j + 1])
j = j + 1;
if (heap->data[k] > heap->data[j])
break;
swap(heap->data, k, j);
然后，k更新为子节点的位置。
k = j;
}
}
递归shiftDown函数
void shiftDown(pmaxHeap heap, int k) {
if (k > heap->count / 2)
return;
int j = 2 * k;
j = heap->data[j] > heap->data[j + 1] ? j : j + 1;
swap(heap->data, j, k);
shiftDown(heap, j);
}
小结
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 100
#define true 1
#define false 0
typedef int bool;
typedef int Item;
typedef struct maxHeap {
Item* data; // 数据数组
int count; // 数量
} maxHeap, *pmaxHeap;
// 初始化maxHeap
void init(pmaxHeap heap, int capacity) {
heap->data = (Item*)malloc(sizeof(Item) * capacity);
heap->count = 0;
}
int size(pmaxHeap heap) { return heap->count; }
bool isEmpty(pmaxHeap heap) { return heap->count == 0; }
void swap(Item* item, int i, int j) {
Item temp = *(item + i);
*(item + i) = *(item + j);
*(item + j) = temp;
}
// void shiftUp(pmaxHeap heap, int k) {
// while (k > 1 && heap->data[k / 2] < heap->data[k]) {
// swap(heap->data, k / 2, k);
// k /= 2;
// }
// }
// void shiftDown(pmaxHeap heap, int k) {
// while (k <= heap->count / 2) {
// int j = 2 * k;
// if (heap->data[j] < heap->data[j + 1])
// j = j + 1;
// if (heap->data[k] > heap->data[j])
// break;
// swap(heap->data, k, j);
// k = j;
// }
// }
// 递归shiftDown
void shiftDown(pmaxHeap heap, int k) {
if (k > heap->count / 2)
return;
int j = 2 * k;
j = heap->data[j] > heap->data[j + 1] ? j : j + 1;
swap(heap->data, j, k);
shiftDown(heap, j);
}
// 递归shiftUp
// void shiftUp(pmaxHeap heap, int k) {
// if (k == 1)
// return;
// if (heap->data[k / 2] >= heap->data[k])
// return;
// swap(heap->data, k / 2, k);
// shiftUp(heap, k / 2);
// }
void shiftUp(pmaxHeap heap, int k) {
if (k == 1)
return;
if (heap->data[k / 2] >= heap->data[k])
return;
swap(heap->data, k / 2, k);
shiftUp(heap, k / 2);
}
// 插入新元素
void insert(pmaxHeap heap, Item item) {
heap->data[++(heap->count)] = item;
shiftUp(heap, heap->count);
}
// 取出堆顶元素（最大值）
Item getHeapMax(pmaxHeap heap) {
if (heap->count == 1) {
heap->count--;
return heap->data[1];
}
int i = 1;
Item item = heap->data[i];
heap->data[i] = heap->data[heap->count--];
shiftDown(heap, i);
return item;
}
// 打印数组
void print(int* arr, int n) {
for (int i = 0; i < n; i++) {
if (i % 10 == 0) {
printf("\n");
}
printf("%d\t", *(arr + i));
}
printf("\n");
}
int main() {
maxHeap heap;
init(&heap, N);
srand((unsigned)time(NULL));
for (int i = 0; i < N; i++) {
insert(&heap, rand() % (N - 0 + 1) + 0);
}
while (heap.count > 1) {
Item max = getHeapMax(&heap);
printf("%d\t", max);
if (heap.count % 10 == 0) {
printf("\n");
}
}
printf("\n");
}