《我的第一本算法书》读书笔记之堆
堆的定义
堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆是线性数据结构，相当于一维数组，有唯一后继。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
堆支持的操作
- build:建立一个空堆；
- insert:向堆中插入一个新元素；
- update：将新元素提升使其符合堆的性质；
- get：获取当前堆顶元素的值；
- delete：删除堆顶元素；
- heapify：使删除堆顶元素的堆再次成为堆。
以上是百度百科对堆的定义
下面拿个实例，分享下我对堆的理解
对下面一组数进行排序
5 2 7 3 6 1 4
第一步：
构建大根堆：要求 父节点 > 子节点
第二步：
堆排序
- 输出堆顶元素
- 重新调整堆
循环操作这两步，直到输出所有数据为止
首先根据图一中的最大元素堆顶元素7 ，输出7
图二：4 放到堆顶，发现子节点的较大节点6 比 堆顶4 大，交换这两个节点
图三： 调整后的堆，堆顶元素为6，当前堆的最大元素为6，输出6
图四： 输出6后的堆，1移到堆顶，发现子节点中较大节点5 大于堆顶1， 交换这两个节点。
图五：1与它较大的子节点3 进行交换
图六： 此时是调整后的堆，堆顶元素 5，输出5
图七： 4移到堆顶元素，得到新的大根堆，堆顶元素为4， 输出4
图八： 3 2 1
得到的数据倒序输出
1 2 3 4 5 6 7