@[TOC]堆详解

一，堆

1.1堆的概念

堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

1.2堆的存储模式

我们前面的文章提到过，二叉树的两种存储模式，一个是顺序存储，一个链式存储。而堆就是顺序存储的典型。

这里还有几个关系式要牢牢记住

1. parent=(child-1)/2
2. leftchild=parent*2+1
3. rightchild=parent*2+2

二，堆的实现

void Swap(HPDataType* p1, HPDataType* p2);
void HeapPrint(HP* php);void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
int HeapTop(HP* php);
bool HeapEmpty(HP* php);

2.1堆的结构

从上面的图我们也能看出其实堆就是数组，所以堆的结构和顺序表的结构是一模一样的。

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

2.2★★★堆的插入

堆的插入和顺序表叶类似，先判断空间是否够大，然后在插入数据，不过堆的插入有一个重点就是向上调整

向上调整

我们在尾插入5的时候，就跟自己的父节点比较，（这里是建小堆）比父节点比较，如果更小那就交换。再跟上面的比较，最坏的情况就是到跟节点，

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){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail!");exit(-1);}php->capacity = newcapacity;php->a = tmp;}php->a[php->size] = x;php->size++;//向上调整AdjustUp(php->a, php->size-1);
}

2.3★★★堆的删除

我们说堆的删除的时候，一般指的是删除跟位置的值，那么我们最开始学习的时候，想到的删除方法就是直接删掉跟，然后底下的数据在依次组成堆，但是我们在这样做的时候就会发现，兄弟变成父与子的关系，那么就不一定会是堆的结构了，因为不论是大堆还是小堆，兄弟节点之间没有大小的区分，所以就不能保证堆的正确建立。
所以我们就有了以下的方法，
1.先把根和最后一个节点交换，然后删掉最后一个节点，
2.在依次向下调整这样就可以保证堆的正确性。

向下调整

向下调整和向上调整思路比较类似，向下调整就是知道了父亲节点的下标，然后依次向下比较。

//向下调整
void AdjustDown(HPDataType* a,int n, int parent)
{int child = parent*2 + 1;while (child<n){if (a[child + 1] > a[child] && child + 1 < n){++child;}if (a[child] > a[parent]){Swap(&a[child],&a[parent]);parent = child;child = parent*2 + 1;}else{break;}}
}

那么堆的删除代码就是：

void HeapPop(HP* php)
{assert(php);assert(php->size > 0);//向下调整Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a,php->size,0);
}

2.4取堆顶的数据

int HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

2.5判断是否为空

bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

三，总结

我们已经把堆的基本框架学完了，下一节我们就要学习堆排序的内容。
还是一样，反复练习百炼成钢。