Implement a minimum (min) heap of integers, and write a driver to demonstrate it
ID: 3680819 • Letter: I
Question
Implement a minimum (min) heap of integers, and write a driver to demonstrate its functionality. Min heaps work the same way as maximum (max) heaps except the a parent is always smaller than its children.
The class your min heap should have the following methods insert: Add a new element to the heap, and bubble up as needed. delete: Remove the first element from the heap and then reheapify. heapSort: Make a copy of the heap, then remove and print each element from the clone. Make sure this doesn’t modify the current heap. print: Prints the elements in the heap in breadth order.
Example Print Out:
Int Min Heap Tester
Populating Heap with values
21
37
49
11
23
1
13
16
33
17
Printing Heap
1
16
11
21
17
49
13
37
33
23
Testing heap sort
1 11 13 16 17 21 23 33 37 49
Removing an element from the heap
The element removed is 1 and the heap now is:
11
16
13
21
17
49
23
37
33
25 17 100 19 36Explanation / Answer
Implement a minimum (min) heap of integers :
If A and B are elements in the heap and B is a child of A, then key(A) key(B).
(This property applies for a min-heap. A max heap would have the comparison reversed). What this tells us is that the minimum key will always remain at the top and greater values will be below it. Due to this fact, heaps are used to implement priority queues which allows quick access to the item with the most priority. Here's an example of a min-heap:
A heap is implemented using an array that is indexed from 1 to N, where N is the number of elements in the heap.
At any time, the heap must satisfy the heap property
array[n] <= array[2*n] // parent element <= left child
and
Driver Program to Determine MIn-Heap Functionality :
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.