你好,游客 登录 注册 搜索
背景:
阅读新闻

二叉堆例程

[日期:2013-05-08] 来源:Linux社区  作者:xiahouzuoxin [字体: ]

二叉堆是一种优先队列的数据结构,具有2种性质:结构性质堆序性。这里讨论都基于最小二叉堆,这种二叉堆对最小元素的访问非常高效。

二叉堆的ADT操作主要包括Insert(插入)和DeleteMin(删除最小元)。

1、结构性质:堆是一棵完全二叉树(若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 都被填满,第 h 层所有的结点都连续集中在最左边),如下图。


(1)因为完全二叉树很有规律,因此可以用一个数组而不需要用指针存储,可以存储成如下形式,其中[0]地址处元素常常用于标记(对于最小二叉堆而言,存储一个非常小的值),这只是为了编程方便,当然也可以不用该标记。


(2)对于数组中任一位置i处的元素,其左儿子在位置2*i上,右儿子在2*i+1上。这条信息很有用,也正因为这样,我们可以很方便的不用指针而只用数组就能访问左右儿子。

2、堆序性:

由于我们想快速的找到最小元,因此最小元应在根上。我们可以以O(1)时间找到最小值。

堆序性指,在一个堆中,每一个节点X,X父亲中的关键字小于(或等于)X中的关键字,根节点除外(因为没有父亲)。


3、插入

 

为将一个元素 X 插入到堆中,我们在下一个可用位置创建一个空穴,否则该堆将不是完全数。如果 X 可以放在该空穴中而不破坏堆的序,那么插入完成。否则,我们把空穴的父节点上的元素移入该空穴中,这样,空穴就朝着根的方向上冒一步。继续改过程直到 X 能被放入空穴中为止。



这样一般的策略叫做上滤( percolate up );新元素在堆中上滤直到找出正确的位置。

linux
相关资讯       二叉堆 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款