文档章节

数据结构与算法08 之堆

乐在克里特
 乐在克里特
发布于 2017/02/23 13:52
字数 853
阅读 1
收藏 0

        优先级队列可以用有序数组来实现,这种做法的问题是,尽管删除最大数据项的时间复杂度为O(1),但是插入还是需要较长的O(N)时间,这是因为必须移动数组中平均一半的数据项以插入新数据项,并在完成插入后,数组依然有序。

        这里介绍实现优先级队列的另一种结构:堆。堆是一种树,并非java和C++等编译语言里的“堆”。由它实现的优先级队列的插入和删除的时间复杂度都是O(logN)。尽管这样删除的时间变慢了一些,但是插入的时间快的多了。当速度非常重要,且有很多插入操作是,可以选择堆来实现优先级队列。堆有如下特点:

        ·它是完全二叉树。即除了树的最后一层节点不需要是满的外,其他的每一层从左到右都完全是满的。

        ·它常常用一个数组实现。用数组实现的完全二叉树中,节点的索引有如下特点(设该节点的索引为x):

             它的父节点的索引为 (x-1) / 2;

             它的左子节点索引为 2*x + 1;

             它的右子节点索引为 2*x + 2。

        ·堆中每个节点的关键字都大于(或等于)这个节点的子节点的关键字。这也是堆中每个节点必须满足的条件。所以堆和二叉搜索树相比,是弱序的。

        向堆中插入数据,首先将数据项存放到叶节点中(即存到数组的最后一项),然后从该节点开始,逐级向上调整,直到满足堆中节点关键字的条件为止。

        从堆中删除数据与插入不同,删除时永远删除根节点的数据,因为根节点的数据最大,删除完后,将最后一个叶节点移到根的位置,然后从根开始,逐级向下调整,直到满足堆中节点关键字的条件为止。具体的看下面的代码:

 

  1. public class Heap {  
  2.       
  3.     private Node[] heapArray;  
  4.     private int maxSize;  
  5.     private int currentSize;  
  6.       
  7.     public Heap(int mx) {  
  8.         maxSize = mx;  
  9.         currentSize = 0;  
  10.         heapArray = new Node[maxSize];  
  11.     }  
  12.       
  13.     public boolean isEmpty() {  
  14.         return (currentSize == 0)? true : false;  
  15.     }  
  16.       
  17.     public boolean isFull() {  
  18.         return (currentSize == maxSize)? true : false;  
  19.     }  
  20.       
  21.     public boolean insert(int key) {  
  22.         if(isFull()) {  
  23.             return false;  
  24.         }  
  25.         Node newNode = new Node(key);  
  26.         heapArray[currentSize] = newNode;  
  27.         trickleUp(currentSize++);  
  28.         return true;  
  29.     }  
  30.     //向上调整  
  31.     public void trickleUp(int index) {  
  32.         int parent = (index - 1) / 2//父节点的索引  
  33.         Node bottom = heapArray[index]; //将新加的尾节点存在bottom中  
  34.         while(index > 0 && heapArray[parent].getKey() < bottom.getKey()) {  
  35.             heapArray[index] = heapArray[parent];  
  36.             index = parent;  
  37.             parent = (parent - 1) / 2;  
  38.         }  
  39.         heapArray[index] = bottom;  
  40.     }  
  41.       
  42.     public Node remove() {  
  43.         Node root = heapArray[0];  
  44.         heapArray[0] = heapArray[--currentSize];  
  45.         trickleDown(0);  
  46.         return root;  
  47.     }  
  48.     //向下调整  
  49.     public void trickleDown(int index) {  
  50.         Node top = heapArray[index];  
  51.         int largeChildIndex;  
  52.         while(index < currentSize/2) { //while node has at least one child  
  53.             int leftChildIndex = 2 * index + 1;  
  54.             int rightChildIndex = leftChildIndex + 1;  
  55.             //find larger child  
  56.             if(rightChildIndex < currentSize &&  //rightChild exists?  
  57.                     heapArray[leftChildIndex].getKey() < heapArray[rightChildIndex].getKey()) {  
  58.                 largeChildIndex = rightChildIndex;  
  59.             }  
  60.             else {  
  61.                 largeChildIndex = leftChildIndex;  
  62.             }  
  63.             if(top.getKey() >= heapArray[largeChildIndex].getKey()) {  
  64.                 break;  
  65.             }  
  66.             heapArray[index] = heapArray[largeChildIndex];  
  67.             index = largeChildIndex;  
  68.         }  
  69.         heapArray[index] = top;  
  70.     }  
  71.     //根据索引改变堆中某个数据  
  72.     public boolean change(int index, int newValue) {  
  73.         if(index < 0 || index >= currentSize) {  
  74.             return false;  
  75.         }  
  76.         int oldValue = heapArray[index].getKey();  
  77.         heapArray[index].setKey(newValue);  
  78.         if(oldValue < newValue) {  
  79.             trickleUp(index);  
  80.         }  
  81.         else {  
  82.             trickleDown(index);  
  83.         }  
  84.         return true;  
  85.     }  
  86.       
  87.     public void displayHeap() {  
  88.         System.out.println("heapArray(array format): ");  
  89.         for(int i = 0; i < currentSize; i++) {  
  90.             if(heapArray[i] != null) {  
  91.                 System.out.print(heapArray[i].getKey() + " ");  
  92.             }  
  93.             else {  
  94.                 System.out.print("--");  
  95.             }  
  96.         }  
  97.     }  
  98. }  
  99. class Node {  
  100.     private int iData;  
  101.     public Node(int key) {  
  102.         iData = key;  
  103.     }  
  104.       
  105.     public int getKey() {  
  106.         return iData;  
  107.     }  
  108.       
  109.     public void setKey(int key) {  
  110.         iData = key;  
  111.     }  
  112. }  

 

 

http://blog.csdn.net/eson_15/article/details/51105955

© 著作权归作者所有

共有 人打赏支持
乐在克里特
粉丝 15
博文 268
码字总数 394729
作品 0
杭州
程序员
Python数据结构总结篇

数据结构篇主要是阅读[Problem Solving with Python](http://interactivepython.org/courselib/static/pythonds/index.html)时写下的阅读记录,当然,也结合了部分[算法导论](http://en.wik...

宅男潇涧
2014/07/06
544
0
数据结构的基本概念

(一)什么是数据结构 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效...

九劫散仙
02/01
0
0
堆和栈的区别

一、预备知识—程序的内存分配 一个由c/C++编译的程序占用的内存分为以下几个部分 1、栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构...

angel_kitty
2017/02/22
0
0
前端你应该了解的数据结构与算法

提到数据结构与算法都感觉这应该是后端要掌握的知识,对前端来说只要写写页面,绑定事件,向后台发发数据就好了,用不到数据结构与算法,也许对于一些数据查找 简单的for循环就能搞定,也许只...

幸福拾荒者
06/29
0
0
算法与数据结构(一):导论篇-算法的重要性

算法与数据结构 算法相当的重要 & 算法无处不在 思考:编译器是如何理解你所写的程序的。 编译器的存在涉及着各种算法。搜索引擎:搜索算法加排序算法 遍历1亿的数据。Google定位信息。 推荐...

天涯明月笙
2017/09/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

深入解析MySQL视图VIEW

Q:什么是视图?视图是干什么用的? A:视图(view)是一种虚拟存在的表,是一个逻辑表,本身并不包含数据。作为一个select语句保存在数据字典中的。   通过视图,可以展现基表的部分数据;...

IT--小哥
50分钟前
2
0
虚拟机学习之二:垃圾收集器和内存分配策略

1.对象是否可回收 1.1引用计数算法 引用计数算法:给对象中添加一个引用计数器,每当有一个地方引用它时,计数器值就加1;当引用失效时,计数器值就减1;任何时候计数器值为0的对象就是不可能...

贾峰uk
今天
2
0
smart-doc功能使用介绍

smart-doc从8月份底开始开源发布到目前为止已经迭代了几个版本。在这里非常感谢那些敢于用smart-doc去做尝试并积极提出建议的社区用户。因此决定在本博客中重要说明下smart-doc的功能,包括使...

上官胡闹
昨天
9
0
JavaEE——Junit

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 Junit Junit又名单元测试,Junit是用来测试Jav...

凯哥学堂
昨天
7
0
读《美丽新世界》

一、背景 十一国庆节从重庆回深圳的时候,做得绿皮车,路上看了两本书:李笑来的《韭菜的自我修养》和禁书《美丽新世界》。 上篇文章已经分享了 读《韭菜的自我修养》,这篇文章来记录一下《...

tiankonguse
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部