设为首页 加入收藏

TOP

堆与堆排序(二)
2017-10-10 14:16:14 】 浏览:5281
Tags:排序
) {  //判断堆是否为空

      return currentSize == 0;

   }

  

   //插入一个节点

   public boolean insert(int key) {

      if(currentSize == maxSize) return false; //已满 不能插入

      Node newNode = new Node(key);

      heapArray[currentSize] = newNode; //先插入到最后

      trickleUp(currentSize++);   //从该节点开始向上筛选,并把currentSize的值加1

      return true;

   }

   //删除一个最大节点(根)

      public Node remove() {

         Node root = heapArray[0];//移除根节点

         heapArray[0] = heapArray[--currentSize];//最后一个节点移动到根节点的位置

         trickleDown(0); //向下筛选

         return root;

      }

 

   //向上筛选

   private void trickleUp(int index) {

      int parent = (index-1)/2;      //先找到父节点索引

      Node bottom = heapArray[index];

      while(index >0 && heapArray[parent].getKey() < bottom.getKey()) {

         //只要index>0且父节点的数据项的值小于自己的值 就继续向上

         heapArray[index] = heapArray[parent];

         index = parent;

         parent = (index-1)/2;

      }

      heapArray[index] = bottom;

   }

  

   //向下筛选

   private void trickleDown(int index) {

      int largeChild;

      Node top = heapArray[index];

      while(index < currentSize/2) { //只要不是叶节点  就继续向下筛选

         //首先获得其左右孩子节点中数值大的那个节点的下标

         int left = index*2+1;

         int right = index*2+2;

         if(right < currentSize && heapArray[left].getKey() < heapArray[right].getKey()) {

            largeChild = right;

         }else {

            largeChild = left;

         }

         //进行值的比较,把值大的子节点与该节点互换,并对值最大的那个节点再继续向下筛选

         if(top.getKey() >= heapArray[largeChild].getKey()) break;

         else {

            heapArray[index] = heapArray[largeChild];

            index  = largeChild;

   &nbs

首页 上一页 1 2 3 4 5 下一页 尾页 2/5/5
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Spring工作原理 下一篇设计模式的思考

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目