你的位置:首页 > 软件开发 > 操作系统 > 算法—二叉堆

算法—二叉堆

发布时间:2015-11-22 22:00:04
实现栈或是队列与实现优先队列的最大不同在于对性能的要求。对于栈和队列,我们的实现能够在常数时间内完成所有操作;而对于优先队列,插入元素和删除最大元素这两个操作之一在最坏情况下需要线性时间来完成。我们接下来要讨论的基于数据结构堆的实现能够保证这两种操作都能更快地执行。 1.堆的 ...

算法—二叉堆

实现栈或是队列与实现优先队列的最大不同在于对性能的要求。对于栈和队列,我们的实现能够在常数时间内完成所有操作;而对于优先队列,插入元素和删除最大元素这两个操作之一在最坏情况下需要线性时间来完成。我们接下来要讨论的基于数据结构堆的实现能够保证这两种操作都能更快地执行。 

算法—二叉堆

1.堆的定义

 数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中,每个元素都要保证大于等于另两个特定位置的元素。相应地,这些位置的元素又至少要大于等于数组中的另两个元素,以此类推。如果我们将所有元素画成一棵二叉树,将每个较大元素和两个较小的元素用边连接就可以很容易看出这种结构。

定义:当一棵二叉树的每个结点都大于等于它的两个子结点时,它被称为堆有序。

相应地,在堆有序的二叉树中,每个结点都小于等于它的父结点(如果有的话)。从任意结点向上,我们都能得到一列非递减的元素;从任意结点向下,我们都能得到一列非递增的元素。

命题:根结点是堆有序的二叉树中的最大结点

证明:根据树的性质归纳可得

二叉堆表示法

如果我们用指针来表示堆有序的二叉树,那么每个元素都需要三个指针来找到它的上下结点(父结点和两个子结点各需要一个)。如下图所示。完全二叉树只用数组而不需要指针就可以表示。具体方法就是将二叉树的结点按照层级顺序放入数组中,根结点在位置1,它的子结点在位置2和3,而子结点的子结点则分别在位置4、5、6和7,以此类推。

算法—二叉堆

定义:二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组中按照层级储存(不使用数组的第一个位置)

简单起见,在下文中我们将二叉堆简称为堆。在一个堆中,位置k的结点的父结点的位置为k/2,而它的两个子结点的位置则分别为2k和2k+1。这样在不使用指针的情况下我们也可以通过计算数组的索引在树中上下移动:从a[k]向上一层就令k等于k/2,向下一层则令k等于2k或2k+1.

用数组(堆)实现的完全二叉树的结构是很严格的,但它的灵活性已经足以让我们高效地实现优先队列。用它们我们将能实现对数级别的插入元素和删除最大元素的操作。利用在数组中无需指针即可沿树上下移动的便利和以下性质,算法保证了对数复杂度的性能。

命题:一棵大小为N的完全二叉树的高度为lgN

证明:通过归纳很容易可以证明这一点,且当N达到2的幂时树的高度会加1

算法—二叉堆

2.堆的算法

 堆的操作会首先进行一些简单的改动,打破堆的状态,然后再遍历堆并按照要求将堆的状态恢复。我们称这个过程叫做堆的有序化。在有序化的过程中我们会遇到两种情况。当某个结点的优先级上升(或是在堆底加入一个新的元素)时,我们需要由下至上恢复堆的顺序。当某个结点的优先级下降(例如将根结点替换为一个较小的元素)时,我们需要由上至下恢复堆的顺序。首先,我们会学习如何实现这两种辅助操作,然后再用它们实现插入元素和删除最大元素的操作。

由下至上的堆有序化(上浮)

private void swim(int k) {    while (k > 1 && less(k/2, k)) {      exch(k, k/2);      k = k/2;    }  }

原标题:算法—二叉堆

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

可能感兴趣文章

我的浏览记录