logo CodeStepByStep logo


Language/Type: C++ heaps
Author: Marty Stepp (on 2016/06/16)

Recall the implementation of a priority queue using a vertically-ordered tree called a heap. Recall that the heap structure "bubbles" elements up and down as they are added and removed to maintain its vertical ordering.

Given the following string/priority pairs:

  • a:60, b:70, c:40, d:30, e:50, f:80, g:20, h:30, i:90, j:10, k:25, l:45

a) Write the final array representation of the binary heap that results when all of the above elements are enqueued (added in the given order) with the given priorities to an initially empty heap. This is a "min-heap", that is, priorities with lesser integer values are higher in the tree. Write your answer in the following format:

{a:17, b:63, c:40}

b) After adding all the elements, perform 2 dequeue operations (remove-min operations) on the heap. Write the final array representation of the heap that results after the two elements are removed, in the same format.

after all enqueues
after 2 dequeues

You must log in before you can solve this problem.

Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.