堆可以利用数组、链表或者搜索二叉树实现,但是最好方法是利用完全二叉树。
1.完全二叉树
完全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐,如下图
重新构建一种树, 专注于插入和删除最大或最小。 即, 根节点总是最大或最小且结构满足完全二叉树。 满足这种结构的树称为堆。
特点:
- 结构性: 用数组表示完全二叉树
- 有序性: 任一节点的关键字是其子树所有节点的最值(最大或最小) 。 最大值者,称为最大堆, “最大堆(MaxHeap)” ,也称“大顶堆” 。 “最小堆(MinHeap)” ,也称“小顶堆” 。
下标性:
当 i=1 时, 该结点为根结点, 它无双亲结点;
当 i>1 时, 其双亲是结点 i/2 (“/” 表示整除);
若 2i≤n, 则第 i 个结点有编号为 2i 的左孩子;
若 2i+1≤n, 则第 i 个结点有编号为 2i+1 的右孩子
2.“最大堆:示例
插入
最大堆的插入操作可以简单看成是“结点上浮”。 当我们在向最大堆中插入一个结点我们必须满足完全二叉树的标准, 那么被插入结点的位置的是固定的。 而且要满足父结点关键字值不小于子结点关键字值,那么我们就需要去移动父结点和子结点的相互位置关系。(不断交换,直到满足最大堆的规则,父节点值大于子节点值)
删除
最大堆的删除操作,总是从堆的根结点删除元素。同样根元素被删除之后为了能够保证该树还是一个完全二叉树,我们需要来移动完全二叉树的最后一个结点,让其继续符合完全二叉树的定义,从这里可以看作是最大堆最后一个结点的下沉。
此时满足的完全二叉树的要求,但是仍然不满足根节点是最大值的要求。继续调整如下:
在已经确定的最大堆中做删除操作,被删除的元素是固定的,需要被移动的结点也是固定的,这里我说的被移动的元素是指最初的移动,即最大堆的最后一个元素。移动方式为从最大的结点开始比较。