bigwheel92 / max-heap Goto Github PK

Implementation of Max Heap data structure in C++ using dynamic arrays.

The following methods are available in the public interface of MaxHeap

-> MaxHeap() : default constructor

-> MaxHeap(int _capacity) : assigns a capacity of given size to the heap.

-> void insert(k const key, v const value) : insert a new <key,value> pair in the heap. The key will be used to maintain heap ordering.

-> void getMax(v & value) : returns the value whose key is maximum via the parameter passed by reference.

-> void deleteMax() : deletes the heap item whose key is maximum

-> bool isEmpty() const : returns true if the heap has no item, else false

-> void deleteAll() : completely destroys the heap. The capacity is set to 0. and the array in the heap is set to nullptr.

-> ~MaxHeap() : destructor

The following private methods are available:

-> void doubleCapacity() : doubles the capacity of heap. For example, if the current capacity of heap is 10, then after calling this function, the capacity will become 20. This method is used by insert method to increase the capacity when the heap is full.

-> void shiftUp(int index) : It is a recursive method that, in a single recursive call, shifts the item stored at given index one step up if its key is greater than the key of its parent. Insert method uses this method to recursivley shift the new item to the root if its key is maximum.

-> void shiftDown(int index) : It is a recursive method that, in a single recursive call, shifts the item stored at given index one step down if its key is smaller than the key of any of its children. deleteMax method uses this method. To delete the max item (the one at index 0), deleteMax method first moves the last item to index 0, and then it calls shiftDown method, starting from index 0, to recursively move down the last item to its appropriate location.