2.7 二叉堆及优先队列
一.二叉树
1.首先介绍一下二叉树
(1)二叉树:每个节点最多有两个子树的结构
(2)完全二叉树:叶节点只能出现在最下层和次下层,并且最下一层的节点集中在该层最左边的若干位置的二叉树
(3)满二叉树:叶节点只能出现在最下层
二.二叉堆(堆)
1.堆有序:当一棵二叉树的每个结点都不小于它的两个子结点时,称为堆有序
2.二叉堆:一组能够用堆有序的完全二叉树排序的元素,并且能在数组中按照层级存储。
3.说明:
(1)二叉堆可以用数组来表示,从1-N,根节点位置在a[1]
(2)二叉堆可以不使用指针而是简单的使用数学关系,来表示结构
(3)位置k的结点的父节点是(int)k/2,两个子结点的位置是2k和2k+1
(4)一颗大小为N的完全二叉树的高度是|_lgN_|
4.堆的维护
(1)上浮。当某个结点比父结点更大时,需要交换它和父结点的位置,并继续判断,直到比父结点小。
private void swim(int k) { while(k>1 && less(k/2,k)) { exch(k,k/2); k=k/2; } }
(2)下沉。当某个结点比它的两个子结点或其中一个子结点小,需要将父结点与子结点中较大的一个进行交换,重复该过程,直到比子结点都大。
private void sink(int k) { while(2*k<=N) { int j=2*k; //考虑到只有左结点的情况 //如果有2个结点,则取最大的结点 if(j<N && less(j,j+1)) j++; //比较子结点和k的大小 if(less(j,k)) break; exch(j,k); k=j; } }