问题插入堆排序 [英] questions Inserting in heapsort

问题描述

import java.util.ArrayList;
import java.util.Collection;

public class MaxHeap
{
   private ArrayList<Student> students;

   public MaxHeap(int capacity)
   {
      students = new ArrayList<Student>(capacity);
   }

   public MaxHeap(Collection<Student> collection)
   {
      students = new ArrayList<Student>(collection);
      for(int i = size()/2; i >= 0; i--)
      {
         maxHeapify(i);
      }
   }

   public Student getMax()
   {
      if(size() < 1)
      {
         throw new IndexOutOfBoundsException("No maximum value:  the heap is empty.");
      }
      return students.get(0);
   }

   public Student extractMax()
   {
      Student value = getMax();
      students.set(0,students.get(size()-1));
      students.remove(size()-1);
      maxHeapify(0);
      return value;
   }


   public void insert(Student elt)
   {

       private int lastOne;

       if (lastOne ==  students.length)
           throw new heapException("heap is full");
       else {
           // I'm stuck here

       }
   }

据我了解，我最后插入了元素。然后将其与其父级进行比较。
如果parent大于此最新插入，则返回该元素。
其他交换父母和这个孩子

As I understand, I Insert the element at last. Then compare it with its parent. If parent is greater than this latest insertion, return the element. Else swap parent and this child

    private int parent(int index)
   {
      return (index - 1)/2;
   }

   private int left(int index)
   {
      return 2 * index + 1;
   }

   private int right(int index)
   {
      return 2 * index + 2;
   }

   private int size()
   {
      return students.size();
   }

   private void swap(int from, int to)
   {
      Student val = students.get(from);
      students.set(from,  students.get(to));
      students.set(to,  val);
   }

   private void maxHeapify(int index)
   {
      int left = left(index);
      int right = right(index);
      int largest = index;
      if (left <  size() && students.get(left).compareTo(students.get(largest)) > 0)
      {
         largest = left;
      }
      if (right <  size() && students.get(right).compareTo(students.get(largest)) > 0)
      {
         largest = right;
      }
      if (largest != index)
      {
         swap(index, largest);
         maxHeapify(largest);
      }  
   }   
}

谢谢大家，现在我可以制作一个子节点和父节点，但是如何添加insert方法呢？我考虑while或if陈述。但是不能解决问题……

Thank you everybody, now i can make a children and parent node, but How can add insert method ? I think about while or if statement. But cannot fingure out...

推荐答案

在基于0的二进制堆中，给定索引为 i ：

In a 0-based binary heap, given a node at index i:

• 左孩子的索引为（i * 2）+ 1


• 正确的孩子在索引（i * 2）+ 2


• 父级位于索引（i-1）/ 2

• The left child is at index (i * 2) + 1
• The right child is at index (i * 2) + 2
• The parent is at index (i - 1)/2

要插入，请将该项目添加为数组中的最后一项，然后将其向上移动到堆中，并与父项进行连续比较。像这样：

To insert, you add the item as the last item in the array, and then you move it up the heap, continually comparing with the parent. Like this:

public void insert(Student elt)
{
    students.add(elt);
    int i = students.size()-1;
    while (i > 0)
    {
        int p = parent(i);
        if (students[i] >= students[p])
        {
            // item is not smaller than parent, so we're done
            break;
        }
        // swap child and parent items
        swap(p, i);

        // and then move up one level
        i = p;
    }
}

这篇关于问题插入堆排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！