Heap Algo 4

You are using the HeapPriorityQueue class implemented with a binary min-heap, which is stored as an array (Python list) in level-order.
The heap currently stores the following key-value pairs:
[(2, 'A'), (4, 'B'), (6, 'C'), (8, 'D'), (5, 'E')]

After calling remove_min() once, what will be the contents of the heap (in array/list format)?
(Assume that the heap properties are restored correctly after the operation.)

Pseudocode for remove_min()

remove_min():
swap the root with the last element
remove the last element (which is the min)
call _downheap(0)

Pseudocode for _downheap(j)

_downheap(j):
if left child exists:
small_child = left
if right child exists and right

Question

Heap Algo 4

You are using the HeapPriorityQueue class implemented with a binary min-heap, which is stored as an array (Python list) in level-order.
The heap currently stores the following key-value pairs:
[(2, 'A'), (4, 'B'), (6, 'C'), (8, 'D'), (5, 'E')]

After calling remove_min() once, what will be the contents of the heap (in array/list format)?
(Assume that the heap properties are restored correctly after the operation.)

Pseudocode for remove_min()

remove_min():
    swap the root with the last element
    remove the last element (which is the min)
    call _downheap(0)

Pseudocode for _downheap(j)

_downheap(j):
    if left child exists:
        small_child = left
        if right child exists and right < left:
            small_child = right
        if small_child < j:
            swap(j, small_child)
            _downheap(small_child)

In this implementation, for an element at index j:

Left child is at index 2j + 1

Right child is at index 2j + 2

Parent is at index (j - 1) // 2

BlackTom AI · Accepted Answer

We start by restating the problem setup and then inspect each answer choice in light of how remove_min and _downheap operate on a binary min-heap stored in an array.
First, the initial heap is [(2, 'A'), (4, 'B'), (6, 'C'), (8, 'D'), (5, 'E')]. When remove_min is called, the typical steps are to swap the root with the last element, remove the last element (the original min), and then restore the heap order by downheaping from the root.
Step-by-step of the operation:
- Swap root with last element: we get [(5, 'E'), (4, 'B'), (6, 'C'), (8, 'D'), (2, 'A')].
- Remove the last element (which is (2, 'A')): heap becomes [(5, 'E'), (4, 'B'), (6, 'C'), (8, 'D')].
- Downheap from index 0: children are at indices 1 and 2, with keys 4 and 6 respectively. The smaller child is (4, 'B'). Since 4 < 5, swap index 0 and 1: we obtain [(4, 'B'), (5, 'E'), (6, 'C'), (8, 'D')].
- Continue downheaping from index 1 (value 5): its only left child is at index 3 with key 8. Since 8 is not smaller than 5, no further swaps occur, and the heap is valid.
Now evaluate each option:
Option 1: [(4, 'B'), (8, 'D'), (6, 'C')] — This sequence is missing (5, 'E') and (8, 'D') occupies a position that would violate the structure after downheap; it does not match the expected result. Therefore this option is incorrect.
Option 2: [(5, 'E'), (4, 'B'), (6, 'C'), (8, 'D')] — After removal and downheap, the root should be the smallest remaining element, which is (4, 'B'); having (5, 'E') at the root contradicts the heap property, so this is incorrect.
Option 3: [(4, 'B'), (8, 'D'), (6, 'C'), (5, 'E')] — This places (8, 'D') as the second element, which would violate the heap ordering since 8 is larger than 5 and 4, and would not be produced by the described downheap process; incorrect.
Option 4: [(4, 'B'), (5, 'E'), (6, 'C'), (8, 'D')] — This matches the step-by-step result obtained above, with (4, 'B') at the root, (5, 'E') as the left child, (6, 'C') as the right child, and (8, 'D') at the next position; it preserves the min-heap property and corresponds to the described algorithm.
In summary, the only option that aligns with the correct swap, removal, and downheap procedure is the one that yields [(4, 'B'), (5, 'E'), (6, 'C'), (8, 'D')].

类似问题

In a min-heap of n elements, implemented with a complete binary tree, the worst case time cost for removeMin() is

A max‑heap is always a:

How many children can a node in a binary heap have?

What is the index of the right child of a node at index i in an Array representation of a Max heap? Assume the cell at index 0 is empty.

What is the index of the right child of a node at index i in an Array representation of a Max heap? Assume the cell at index 0 is empty.

What is the index of the right child of a node at index i in an Array representation of a Max heap? Assume the cell at index 0 is empty.

What are the parent and child indices for node 7 in the following max-heap?

Identify the new binary max-heap after inserting 60 in the following max-heap.

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单