前言
在前面的学习中，我们实现了栈与队列的实现。今天我们就通过顺序表来实现二叉树！
一. 二叉树的顺序结构
我们如何让顺序表和二叉树建立联系呢？
我们可以先对二叉树的每个结点进行编号，通过数组的连续排列建立以下联系：
这样我们就可以通过数组的下标来模拟实现二叉树了！
但是普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。
所以我们的数组存储表示二叉树只适合完全二叉树。
二.堆的概念及结构
简单的来说，堆就是一颗完全二叉树，并且有以下性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
其中分为小根堆和大根堆：
小根堆：
树中所有父亲都小于等于孩子：
大根堆：
树中所有父亲都大于等于孩子
注意：
在数据结构里面我们所学的栈，堆都是一种数据结构，他们与操作系统
中的栈和堆是两回事，一个是数据结构，一个是操作系统相关的知识，一定不要搞混淆！
三.堆的实现：
typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; void HeapInit(HP* php); void HeapDestroy(HP* php); void HeapPush(HP* php, HPDataType x); void HeapPop(HP* php); HPDataType HeapTop(HP* php); bool HeapEmpty(HP* php); int HeapSize(HP* php); void AdjustUp(HPDataType* a, int child); void AdjustDown(HPDataType* a, int n, int parent);
1.堆的插入(向上调整算法）：
先插入一个数到数组的尾上，再进行向上调整算法，直到满足堆。
向上调整算法的条件是：
除了child结点，之前的结点都是堆
代码实现：
void AdjustUp(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child>0) { if (a[child] > a[parent]) { swap(&a[child],&a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void HeapPush(HP* php, HPDataType x) { assert(php); if (php->capacity == php->size) { HPDataType* ptr = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2); if (ptr == NULL) { perror("realloc::fail"); return; } php->a = ptr; php->capacity *= 2; } php->a[php->size] = x; php->size++; AdjustUp(php->a, php->size-1); }
2.堆的删除（向下调整算法）：
在这里删除堆是指删除堆顶的数据，因为删除堆尾元素没有什么实际的意义。将堆顶的数据与最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
向下调整算法的条件是：
左右子树都为堆！
代码实现：
void HeapPop(HP* php) { assert(php); assert(!HeapEmpty(php)); // 删除数据 Swap(&php->a[0], &php->a[php->size - 1]); php->size--; AdjustDown(php->a, php->size, 0); } void AdjustDown(HPDataType* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { // 选出左右孩子中大的那一个 if (child + 1 < n && a[child+1] > a[child]) { ++child; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
3.堆的构建：
这里建议把后面的堆排序看了在来看这段代码：
void HeapInitArray(HP* php, int* a, int n) { assert(php); php->a = (HPDataType*)malloc(sizeof(HPDataType) * n); if (php->a == NULL) { perror("malloc fail"); return; } php->size = n; php->capacity = n; // 建堆 for (int i = (n-2)/2; i >= 0; --i) { AdjustDown(php->a, php->size, i); } }
这里的意思是给你一个属数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。
