from HeapInt import * \'\'\'* * An implementation of a minimum heap with handles
ID: 3846268 • Letter: F
Question
from HeapInt import *
'''*
* An implementation of a minimum heap with handles
'''
class Heap:
def __init__(self):
'''
The constructor has been set up with an initial array of size 4
so that your doubleHeap() method will be tested. Don't change
this!
'''
self.array = [0]*4
self.heapsize = 0
self.arraysize = 4
def exchange(self, pos1, pos2):
'''
Exchanges that values at positions pos1 and pos2 in the heap array.
Handles must be exchanged correctly as well.
Running time = O(????)
'''
# Provide your implementation here
def doubleHeap(self):
'''
Doubles the size of the array. A new array is created, the elements in
the heap are copied to the new array, and the array data member is set
to the new array. Data member arraysize is set to the size of the
new array.
Running time = O(????)
'''
# Provide your implementation here
def heapifyDown(self, pos):
'''
Fixes the heap if the value at position pos may be bigger than one of
its children. Using exchange() to swap elements will simplify your
implementation. HeapElts contain records, and records contain
keys; you will need to decide how to handle comparisons.
Running time = O(????)
'''
# Provide your implementation here
def heapifyUp(self, pos):
"""
Fixes the heap if the value at position pos may be smaller than its
parent. Using exchange() to swap elements will simplify your
implementation. HeapElts contain records, and records contain
keys; you will need to decide how to handle comparisons.
Running time = O(????)
"""
# Provide your implementation here
def insert(self, inElt):
'''
Insert inElt into the heap. Before doing so, make sure that there is
an open spot in the array for doing so. If you need more space, call
doubleHeap() before doing the insertion.
Running time = O(????) (NOTE that there are a couple of different cases
here!)
'''
# Provide your implementation here
def removeMin(self):
'''
Remove the minimum element from the heap and return it. Restore
the heap to heap order. Assumes heap is not empty, and will
cause an exception if the heap is empty.
Running time = O(????)
'''
# Provide your implementation here
def getHeapsize(self):
'''
Return the number of elements in the heap..
Running time = O(????)
'''
# Provide your implementation here
def printHeap(self):
'''
Print out the heap for debugging purposes. It is recommended to
print both the key from the record and the handle.
Running time = O(????)
'''
# Provide your implementation here
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 (leftRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.