• 近期将进行后台系统升级,如有访问不畅,请稍后再试!
  • 极客文库-知识库上线!
  • 极客文库小编@勤劳的小蚂蚁,为您推荐每日资讯,欢迎关注!
  • 每日更新优质编程文章!
  • 更多功能模块开发中。。。

堆其实是个很简单的数据结构

说到这种数据结构,很多人的第一反应是感觉很复杂,其实不然,就是个优先级队列而已,或者,其实就是一种树。本文先讲原理,后面给出的实现代码。
优先级队列可以用有序数组来实现,这种做法的问题是,尽管删除最大数据项的时间复杂度为 O(1),但是插入还是需要较长的 O(N)时间,这是因为必须移动数组中平均一半的数据项以插入新数据项,并在完成插入后,数组依然有序。
本文主要介绍实现优先级队列的另一种结构:是一种树,并非 java 和 C++等编译语言里的“堆”。由它实现的优先级队列的插入和删除的时间复杂度都是 O(logN)。尽管这样删除的时间变慢了一些,但是插入的时间快的多了。当速度非常重要,且有很多插入操作是,可以选择堆来实现优先级队列。堆有如下特点:
  • 它是完全二叉树。即除了树的最后一层节点不需要是满的外,其他的每一层从左到右都完全是满的。
  • 它常常用一个数组实现。用数组实现的完全二叉树中,节点的索引有如下特点(设该节点的索引为 x):
    它的父节点的索引为 (x-1) / 2; 它的左子节点索引为 2x + 1; 它的右子节点索引为 2x + 2。
  • 堆中每个节点的关键字都大于(或等于)这个节点的子节点的关键字。这也是堆中每个节点必须满足的条件。所以堆和二叉搜索树相比,是弱序的。
向堆中插入数据,首先将数据项存放到叶节点中(即存到数组的最后一项),然后从该节点开始,逐级向上调整,直到满足堆中节点关键字的条件为止。
从堆中删除数据与插入不同,删除时永远删除根节点的数据,因为根节点的数据最大,删除完后,将最后一个叶节点移到根的位置,然后从根开始,逐级向下调整,直到满足堆中节点关键字的条件为止。
原理就这么多,堆真的很简单
下面给出堆的实现代码:
  1. publicclassHeap{
  2.    privateNode[] heapArray;
  3.    privateint maxSize;
  4.    privateint currentSize;
  5.    publicHeap(int mx){
  6.        maxSize = mx;
  7.        currentSize =0;
  8.        heapArray =newNode[maxSize];
  9.    }
  10.    publicboolean isEmpty(){
  11.        return(currentSize ==0)?true:false;
  12.    }
  13.    publicboolean isFull(){
  14.        return(currentSize == maxSize)?true:false;
  15.    }
  16.    publicboolean insert(int key){
  17.        if(isFull()){
  18.            returnfalse;
  19.        }
  20.        Node newNode =newNode(key);
  21.        heapArray[currentSize]= newNode;
  22.        trickleUp(currentSize++);
  23.        returntrue;
  24.    }
  25.    //向上调整
  26.    publicvoid trickleUp(int index){
  27.        int parent =(index -1)/2;//父节点的索引
  28.        Node bottom = heapArray[index];//将新加的尾节点存在 bottom 中
  29.        while(index >0&& heapArray[parent].getKey()< bottom.getKey()){
  30.            heapArray[index]= heapArray[parent];
  31.            index = parent;
  32.            parent =(parent -1)/2;
  33.        }
  34.        heapArray[index]= bottom;
  35.    }
  36.    publicNode remove(){
  37.        Node root = heapArray[0];
  38.        heapArray[0]= heapArray[--currentSize];
  39.        trickleDown(0);
  40.        return root;
  41.    }
  42.    //向下调整
  43.    publicvoid trickleDown(int index){
  44.        Node top = heapArray[index];
  45.        int largeChildIndex;
  46.        while(index < currentSize/2){//while node has at least one child
  47.            int leftChildIndex =2* index +1;
  48.            int rightChildIndex = leftChildIndex +1;
  49.            //find larger child
  50.            if(rightChildIndex < currentSize &&  //rightChild exists?
  51.                    heapArray[leftChildIndex].getKey()< heapArray[rightChildIndex].getKey()){
  52.                largeChildIndex = rightChildIndex;
  53.            }
  54.            else{
  55.                largeChildIndex = leftChildIndex;
  56.            }
  57.            if(top.getKey()>= heapArray[largeChildIndex].getKey()){
  58.                break;
  59.            }
  60.            heapArray[index]= heapArray[largeChildIndex];
  61.            index = largeChildIndex;
  62.        }
  63.        heapArray[index]= top;
  64.    }
  65.    //根据索引改变堆中某个数据
  66.    publicboolean change(int index,int newValue){
  67.        if(index <0|| index >= currentSize){
  68.            returnfalse;
  69.        }
  70.        int oldValue = heapArray[index].getKey();
  71.        heapArray[index].setKey(newValue);
  72.        if(oldValue < newValue){
  73.            trickleUp(index);
  74.        }
  75.        else{
  76.            trickleDown(index);
  77.        }
  78.        returntrue;
  79.    }
  80.    publicvoid displayHeap(){
  81.        System.out.println("heapArray(array format): ");
  82.        for(int i =0; i < currentSize; i++){
  83.            if(heapArray[i]!=null){
  84.                System.out.print(heapArray[i].getKey()+" ");
  85.            }
  86.            else{
  87.                System.out.print("--");
  88.            }
  89.        }
  90.    }
  91. }
  92. classNode{
  93.    privateint iData;
  94.    publicNode(int key){
  95.        iData = key;
  96.    }
  97.    publicint getKey(){
  98.        return iData;
  99.    }
  100.    publicvoid setKey(int key){
  101.        iData = key;
  102.    }
  103. }
这个实现的代码,可以在等公交的时候、吃饭排队的时候拿来看看,利用碎片化时间来学习。

丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:堆其实是个很简单的数据结构
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

欢迎 注册账号 登录 发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00