1 二叉树的顺序结构
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆 ( 一种二叉树 ) 使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
2 堆的概念及结构
如果有一个关键码的集合 K = { k0 ，k1 ，k2 ，k3 … ，} ，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <=K2i+1 且 Ki<=K2i+2 ( i = 0 ， 1 ， 2… )，则称为小堆 (反之则大堆 ) 。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树
3 堆的实现
3.1 堆向下调整算法
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提： 左右子树必须是一个堆，才能调整。
int array [] = { 27 , 15 , 19 , 18 , 28 , 34 , 65 , 49 , 25 , 37 };
具体代码：
void AdjustDown(int* a, int parent, int sz) { assert(a); int child = parent * 2 + 1; while (child < sz) { if (child + 1 < sz && a[child + 1] > a[child])//建立小堆 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.2 堆向上调整算法
堆的向上调整算法往往与push相搭配，push完一个数据就将该数据向上调整，这样就能够保证堆的结构不会被破坏。
代码实现：
void AdjustUp(int* a, int child) { assert(a); int parent = (child - 1) / 2; while (child>0)//用parent>=0也行，只是这样的话就不是正常结束的了 { if (a[child] > a[parent])//建小堆 < { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else break; } }
我们不难发现一个数据向上调整或者向下调整的时间复杂度都为logN.
3.3堆的插入
代码实现：
void HeapPush(Heap* php, HeapDataType x) { assert(php); if (php->capacity == php->sz) { int newcapacity = php->a == NULL ? 4 : php->capacity * 2; HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail:"); exit(-1); } php->a = tmp; php->capacity = newcapacity; } php->a[php->sz] = x; php->sz++; //向上调整算法，保证建立的是堆（这里以建小堆为例） AdjustUp(php->a, php->sz - 1);//第二个参数传的是push这个数据的下标 }
3.4 堆的删除
假设建小堆，要pop掉最小的一个数值（堆顶），要让下面的结构继续保持小堆结构就不能只将数据向前挪动一位，否则堆的结构将会被破坏。正确做法是将堆顶的数据与最后一个数据交换，然后重新向下建堆，再pop掉堆尾数据。
代码实现：
void HeapPop(Heap* php) { assert(php); assert(php->sz > 0); //假设建小堆，要pop掉最小的一个数值（堆顶），要让下面的结构继续保持小堆结构就不能只将数据向前挪动一位， //否则堆的结构将会被破坏。正确做法是将堆顶的数据与最后一个数据交换，然后重新向下建堆，再pop掉堆尾数据。 Swap(&php->a[0], &php->a[php->sz - 1]); php->sz--; AdjustDown(php->a, 0, php->sz); }
