黑马程序员技术交流社区

标题: 堆 [打印本页]
作者: 浅易    时间: 2015-10-26 02:00
标题: 堆
最大顶堆是如何实现的？看书一直有点蒙
作者: 叶子和大人    时间: 2015-10-26 02:00
  1. //向最大堆中插入元素, heap:存放堆元素的数组  
  2.    public static void insert(List<Integer> heap, int value) {   
  3.       //在数组的尾部添加  
  4.        if(heap.size()==0)  
  5.          heap.add(0);//数组下标为0的位置不放元素  
  6.        heap.add(value);   
  7.        //开始上升操作   
  8.       // heapUp2(heap, heap.size() - 1);   
  9.        heapUp(heap, heap.size() - 1);   
  10.   
  11.    }   
  12.   
  13.    //上升，让插入的数和父节点的数值比较，当大于父节点的时候就和父节点的值相交换   
  14.    public static void heapUp(List<Integer> heap, int index) {   
  15.   
  16.        //注意由于数值是从下标为1开始，当index = 1的时候，已经是根节点了   
  17.        if (index > 1) {   
  18.            //求出父亲的节点   
  19.            int parent = index / 2;   
  20.   
  21.            //获取相应位置的数值   
  22.            int parentValue = (Integer) heap.get(parent);   
  23.            int indexValue = (Integer) heap.get(index);   
  24.            //如果父亲节点比index的数值小，就交换二者的数值   
  25.            if (parentValue < indexValue) {   
  26.                //交换数值   
  27.                swap(heap, parent, index);   
  28.                //递归调用   
  29.                heapUp(heap, parent);   
  30.            }   
  31.   
  32.        }   
  33.    }   
复制代码

代码就是这样了看不懂没关系，数据结构可以不用学那么深。java中用到比较少。
作者: gdhyxh    时间: 2015-10-26 08:54
实例对象的时候，new出来的
作者: Kris    时间: 2015-10-26 10:18
这个貌似涉及到完全二叉树的算法问题，感觉好难啊~
作者: 南烟    时间: 2015-10-26 12:03
这个应该是数据结构这门课的知识!
假设有n个元素的堆，输出堆顶元素后，剩下n-1个元素。将堆底元素送入堆顶，堆被破坏，其原因是根节点不满足堆的性质，但左右子树都满足堆的性质。将根结点与左右孩子中较大的进行交换。如与左孩子交换，则堆的左子树被破坏，且仅左子树的根结点不满足堆的性质；与右孩子交换同理。继续对不满足的结点进行上述交换操作就OK了
作者: xingjiyuan26    时间: 2015-10-26 15:53
这是哪一部分的知识。。看来这一部分属于不知道自己不知道的
作者: Mu。    时间: 2015-10-26 18:09
霸气威武。。。。。
作者: 大头爱傻瓜    时间: 2015-11-2 17:42
不懂,什么方面的知识



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2