import java.util.ArrayList;
import java.util.Collection;
public class MaxHeap
{
private ArrayList students;
public MaxHeap(int capacity)
{
students = new ArrayList(capacity);
}
public MaxHeap(Collection collection)
{
students = new ArrayList(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
}
}
< /code>
Как я понимаю, я наконец вставляю элемент. Затем сравните его со своим родителем.
Если родитель больше, чем эта последняя вставка, верните элемент.
else Swap Parent и этого ребенка < /p>
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);
}
}
}
< /code>
Спасибо всем, теперь я могу завести детей и родительского узла, но как добавить метод вставки? Я думаю о том, что или если утверждение. Но не может выключиться ...
Подробнее здесь: https://stackoverflow.com/questions/485 ... n-heapsort
