Design and implement a min heap collection, with an appropriate interface, imple

Question

Design and implement a min heap collection, with an appropriate interface, implementing class, and node class, Use a linked implementation strategy.

Explanation / Answer

import java.util.*; /** * Minimum heap implementation. See [Cormen et al 1999] for formal theory. * Maintains all elements in a min-heap, such that the minimum element will * be the top-most node in the heap at all times. Among many other uses, heaps are ideal for * representing priority queues. */ public class Heap { private int size; final private List heap; final private Comparator comparator; private class Node { public T element; public int position; } /** * Create a new heap * @param comparator A comparator that handles elements of type T */ public Heap( Comparator comparator ) { size = 0; //Allocate space heap = new ArrayList(); //Comparator this.comparator = comparator; //initialy clear //for (int i=0;i0) { minHeapify( heap.get(0) ); } return returnNode; } // private final void reinsert( final Node n ) { // if ( !decreaseKey(n) ) { // minHeapify(n); // } // } public final int size() { return size; } private final boolean decreaseKey( final Node node ) { int index = node.position; boolean modified = false; // while ( index>0 && (heap[parent(index)]).compareTo( heap[index]) >= 0 ) { while ( index>0 && comparator.compare(heap.get(parent(index)).element, heap.get(index).element ) >= 0 ) { exchange( index, parent(index) ); index = parent(index); modified = true; } return modified; } private final void minHeapify( final Node node ) { int smallest; int index = node.position; int left = left(index); int right = right(index); // if (left

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.