二叉堆

容易证明:

一棵高为h的完全二叉树有2^h 到 2^(h+1)-1个结点。

这就意味着,完全二叉树的高是[logN]

特点:

任意位置i:

左儿子在位置2i上,右儿子在位置2i+1上,父亲在i/2上

一个堆数据结构将由一个Comparable数组和一个代表当前堆的大小的整数组成:

优先队列的接口:

 1 template <typename Comparable>
 2 class BinaryHeap
 3 {
 4 public:
 5     explicit BinaryHeap ( int capacity = 10 );
 6     explicit BinaryHeap ( const Vector<Comparable> & items);
 7 
 8     bool isEmpty() const;
 9     const Comparable & findMin() const;
10 
11     void insert(const Comparable & x);
12     void deleteMin();
13     void deleteMin(Coparable & minItem);
14     void makeEmpty();
15 private:
16     int currentSize;
17     vector<Comparable> array;
18     void buildHeap();
19     void percolateDown(int hole);
20 }

堆序的性质:如果想要找到一个最小点,最好是把最小值移动到堆的最上方,使用方法: 上滤

应用比如插入一个元素到堆中:

 1 void insert(const Comparable & x)
 2 {
 3     if(currentSize == array.size()-1)
 4         array.resize(array.size()*2);
 5 
 6     int hole = ++currentSize;
 7 
 8     for( ; hole > 1 && x < array[hole/2];hole /= 2)
 9         array[hole] = array[hole/2];
10     array[hole] = x;
11 }

想要删除一个堆结点,一般都是要把堆结点移动到最顶端,然后通过 下滤 方法删除:

 1 void deletMin()
 2 {
 3     if(isEmpty())
 4         throw UnderflowException();
 5 
 6     array[1] = array[currentSize--];
 7     percolateDown(1);
 8 }
 9 void deleteMin(Comparable & minItem)
10 {
11     if(isEmpty())
12         throw UnderflowException();
13     minItem = array[1];
14     array[1] = array[currentSize--];
15     percolateDown(1);
16 }
17 void percolateDown(int hole)
18 {
19     int child;
20     Comparable tmp = array[hole];
21     for( ; hole*2 <= currentSize;hole = child)
22     {
23         child = hole*2;
24         if(child != currentSize && array[child+1] < array[child])
25             child++;
26         if(array[child] < tmp)
27             array[hole] = array[child];
28         else
29             break;
30     }
31     array[hole] = tmp;
32 }

堆的其他操作:

decreaseKey(p,@):把p结点的元素减少到p-@

increaseKey (p,@):把p结点的元素增加到p+@

remove (p)一般都是先用decreaseKey(p,无限大),减少到最小,然后移动至堆顶端,用deleteMin方法删除。

buildHeap:构造堆原始集合

 1 explicit BinaryHeap( const vector<Comparable> & items): array(item.size()+10),currentSize(items.size())
 2 {
 3     for(int i=0;i<items.size();i++)
 4         array[i+1] = items[i];
 5     buildHeap();
 6 }
 7 void buildHeap()
 8 {
 9     for( int i = currentSize/2; i>0;i--)
10         percolateDown(i);
11 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

HashSet 源码分析【面试+工作】

在工作中,经常有这样的需求,需要判断某个ID是否在某个组的管理之下等,就需要查询该组下的ID放到一个集合中,且集合中元素不能有重复,之后判断该集合是否包含我们的...

12630
来自专栏软件开发 -- 分享 互助 成长

java中大数类的学习

java中提供了大数类BigInteger和BigDecimal分别表示大整数类和大浮点数类,这两个类都在java.math.*包中,因此每次必须在开头处引用该...

25350
来自专栏赵俊的Java专栏

LeetCode 804 Unique Morse Code Words

首先为每个单词的每个字符进行转码, 将转码后的数据放到 Set 集合中, 最后返回 Set 的长度。

11040
来自专栏码匠的流水账

聊聊storm nimbus的mkAssignments

storm-2.0.0/storm-server/src/main/java/org/apache/storm/daemon/nimbus/Nimbus.jav...

13320
来自专栏Android知识点总结

Java总结之容器家族--Collection

Set的操作比较少,基本上也就是Collection传下来的方法 Set一般基于Map来实现:HashSet、LinkedHashSet、TreeSet的特性...

17120
来自专栏用户画像

6.2.2 折半查找

折半查找,又称二分查找,它适用于有序的顺序表。基本思路是:首先将给定值key与表中中间位置元素的关键字比较,若相等,则查找成功,返回该元素的存储位置;若不等,则...

7310
来自专栏Java学习123

【数据结构】ArrayList原理及实现学习总结

90950
来自专栏老马说编程

(41) 剖析HashSet / 计算机程序的思维逻辑

查看历史文章,请点击上方链接关注公众号。 上节介绍了HashMap,提到了Set接口,Map接口的两个方法keySet和entrySet返回的都是Set,本节,...

19290
来自专栏JAVA高级架构

Java数据结构与算法解析——2-3树

二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,...

40470
来自专栏IMWeb前端团队

ES6 Set

本文作者:IMWeb kurtshen 原文出处:IMWeb社区 未经同意,禁止转载 ES6 Set ES6 新增了几种集合类型,本文主要介绍Set以...

18670

扫码关注云+社区

领取腾讯云代金券