堆

Heap（堆），是一种数据结构
它具有以下特点

• 总是完全二叉树
• 堆中某个节点的值总是不大于或不小于其父节点的值

Min-heap（小根堆）: 父节点的值小于或等于子节点的值
Max-heap（大根堆）: 父节点的值大于或等于子节点的值

关于线性存储结构和非线性存储结构

线性结构：结构中的数据元素存在着一对一的关系。也就是只有一个前驱一个后继。
所以说，队列，栈，堆都是线性存储。
二叉树是非线性存储。

堆虽然在逻辑上是树状的。但是在存储形式上仍然是顺序存储的。

堆的存储

一般都用数组来表示堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2 i + 1和2 i + 2。如第0个结点左右子结点下标分别为1和2。

由于堆存储在下标从0开始计数的数组中，因此，在堆中给定下标为i的结点时：
（1）如果i=0，结点i是根结点，无父结点；否则结点i的父结点为结点(i-1)/2；
（2）如果2i+1>n-1，则结点i无左子女；否则结点i的左子女为结点2i+1；
（3）如果2i+2>n-1，则结点i无右子女；否则结点i的右子女为结点2i+2。

小根堆的插入和删除

原文：https://www.cnblogs.com/WindSun/p/11444446.html#top
这里自己记录一下。在做面试题的时候，这里有点忘了。