二叉树--堆

一、堆的概念及结构

1.1 堆的概念与结构

堆就是完全二叉树以顺序存储方式存储于一个数组中。

然后每一个根都大于它的左孩子和右孩子的堆，我们叫做大堆，上图就是一个典型的大堆，小堆就是每一个根都小于它的左孩子和右孩子的堆。

这个就是一个小堆。

1.2 堆的性质

1、堆中某个结点的值总是不大于或不小于其父结点的值；
2、堆总是一棵完全二叉树

3、
这里的规律在堆的实现中会使用到，希望大家可以记住。

二、堆的实现

我们这里使用的是顺序结构，所以我们可以采用之前的顺序表来存储。

1、先定义一个堆

typedef int type;typedef struct Heap
{type* arr;int size;int capacity;
}HP;

这一部分在之前顺序表的章节讲过，所以在这里我就不多讲了。

2、堆的初始化和销毁。

void HpInit(HP* ptr)
{assert(ptr);ptr->arr = NULL;ptr->capacity = ptr->size = 0;
}
void HpDestroy(HP* ptr)
{assert(ptr);free(ptr->arr);ptr->capacity = ptr->size = 0;
}

3、堆的插入

插入部分跟之前一样，但是我们插入后需要进行一系列操作

比如说现在我们将1插入，但是我们插完1后还是小堆吗？那我们是不是要让这个1向上调整啊，我们的向上调整走的是下面的过程：

如果孩子小于父亲，孩子和父亲就交换，直到父亲小于孩子（小堆），大堆则反过来。
代码：

void swap(int* p, int* q)//交换父亲和孩子，这一部分向下调整也会用到，所以封装起来
{int tep = *p;*p = *q;*q = tep;
}
void adjustUp(type* arr, int size)
{int child = size - 1;//size是数组元素个数，下标等于元素个数 -1int parent = (child - 1) / 2;//根据上面的公式，用孩子求父亲while (child > 0){if (arr[parent] > arr[child]){swap(&arr[parent], &arr[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}
void HpPush(HP* ptr, type x)
{assert(ptr);if (ptr->capacity == ptr->size){int newcapacity = ptr->capacity == 0 ? 4 : 2 * ptr->capacity;type* tep = (type*)realloc(ptr->arr, sizeof(type)* newcapacity);if (tep == NULL){perror("realloc");return;}ptr->arr = tep;ptr->capacity = newcapacity;}ptr->arr[ptr->size++] = x;adjustUp(ptr->arr, ptr->size);
}

那上面的会写了以后，我们再想想我们怎样将一个数组给建成堆呢？
我们是不是可以将数组一个元素一个元素的入堆，每入一个元素就向上调整一次，那这样我们的堆是不是就建好了。

大家可以看到我们成功的建了一个小堆。

4、堆的删除

堆的删除跟之前不太一样，我们要是删除堆最后一个元素，对我们的堆有影响吗？
所以我们删除的是堆顶的元素，在删除堆顶的元素后要保证我们还是一个大堆或者小堆。
如果我们直接删就会出现下面的情况：

所以我们要先进行一步操作，交换第一个元素和最后一个元素，这样我们删除最后一个元素是不会影响我们的堆的次序的，然后我们在进行一个向下调整，在调整时我们一定要想好交换哪个孩子，如果我们建的是小堆，那么就交换我们小的孩子，大堆就交换大的孩子。

代码：

void adjustDown(type* arr, int parent, int size)
{int child = parent * 2 + 1;while (child < size){if (child + 1 < size && arr[child] > arr[child + 1])//找到小的孩子{child++;}if (arr[parent] > arr[child]){swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}
void HpPop(HP* ptr)
{assert(ptr);swap(&ptr->arr[0], &ptr->arr[ptr->size - 1]);ptr->size--;adjustDown(ptr->arr, 0, ptr->size);
}

5、取堆顶元素

这块比较简单，我就直接给代码了

type HpTop(HP* ptr)
{assert(ptr);assert(ptr->size > 0);return ptr->arr[0];
}

6、判空

bool HpisEmpty(HP* ptr)
{assert(ptr);return ptr->size == 0;
}

7、直接用顺序表建堆

上面我们是将元素放入我们的堆后再进行其他操作，但实际上我们可以直接在顺序表里建堆。

这样就直接建堆了，这里是将数组看做完全二叉树。

三、堆的应用

1、堆排序

堆排序就是后面我们所说的八大排序之一的堆排，那这个怎么实现？

堆排序走的是这样的一个过程，首先先建好一个堆，然后交换第一个元素和最后一个元素，因为堆顶一定是我们最大或最小的元素，所以最后一个元素就排好了，接下来我们进行一次向下调整，选出次小的在我们的堆顶，然后交换堆顶与倒数第一个元素，这样倒数第二个元素就排好了，直到排完整个数组。

这里我排的是逆序的，为什么这里是逆序的呢？这是因为我们建的小堆，我们选小的在我们的数组末尾，那我们是不是可以总结一个规律啊！
建大堆——排升序
建小堆——排逆序

2、向下调整建堆

这个算法虽然可以用，但是它的效率并没有我们的向上调整建堆高，所以这里我不讲。

7、TopK

上面这些完成了我们就可以简单的打印我们这里的排序了，这个问题也叫做TopK问题，注意的是这里并没有进行排序，只是将我们有序的数给打印出来。

void test1()
{HP hp;HpInit(&hp);int arr[] = { 1,5,2,8,0,4,3,7 };for (int i = 0; i < sizeof(arr) / sizeof(int); i++){HpPush(&hp, arr[i]);}//可以将我们的排序打印出来，但是这里并没有进行真正的排序while (!HpisEmpty(&hp)){printf("%d ", HpTop(&hp));//取堆顶元素，直到堆为空HpPop(&hp);//取一个元素，删除一个元素}HpDestroy(&hp);
}
int main()
{test1();return 0;
}

这里我写的时候元素给的比较少，我们可以改一下，

这里我们在数组里放了10000个元素，然后我们求最小的10个，这就是TopK。

总的来说这一章难度在上升，大家下来多理解这里的向上调整、向下调整以及我们的排序的过程，相信大家一定可以学好的。