1

I am working on a problem about building a min heap from an array. I have 2 approaches - the first is recursion and the second is using a while loop. The recursion approach passed the tests on the online grader, but the while loop version doesn't seem to work. I generated some random stress tests in my code below and found that the 2 methods gave different answers as well.

May I know what's the mistake in my second method? The question is as follows:

Input Format. The first line of the input contains single integer 𝑛. The next line contains 𝑛 space-separated integers 𝑎𝑖.

Constraints. 1 ≤ 𝑛 ≤ 100 000; 0 ≤ 𝑖, 𝑗 ≤ 𝑛 − 1; 0 ≤ 𝑎0, 𝑎1,..., 𝑎𝑛−1 ≤ 109. All 𝑎𝑖 are distinct.

Output Format. The first line of the output should contain single integer 𝑚 — the total number of swaps.

𝑚 must satisfy conditions 0 ≤ 𝑚 ≤ 4𝑛. The next 𝑚 lines should contain the swap operations used to convert the array 𝑎 into a heap. Each swap is described by a pair of integers 𝑖, 𝑗 — the 0-based indices of the elements to be swapped. After applying all the swaps in the specified order the array must become a heap, that is, for each 𝑖 where 0 ≤ 𝑖 ≤ 𝑛 − 1 the following conditions must be true:

  1. If 2𝑖 + 1 ≤ 𝑛 − 1, then 𝑎𝑖 < 𝑎2𝑖+1.
  2. If 2𝑖 + 2 ≤ 𝑛 − 1, then 𝑎𝑖 < 𝑎2𝑖+2.

Note that all the elements of the input array are distinct. Note that any sequence of swaps that has length at most 4𝑛 and after which your initial array becomes a correct heap will be graded as correct.

My code:

# python3

from random import randint

swaps = []

def sift_down(i, n, data):
    min_index = i
    left_child = 2*i + 1
    right_child = 2*i + 2
    if left_child < n and data[left_child] < data[min_index]:
        min_index = left_child
    if right_child < n and data[right_child] < data[min_index]:
        min_index = right_child
    if i != min_index:
        swaps.append([i, min_index])
        data[i], data[min_index] = data[min_index], data[i]
        sift_down(min_index, n, data)

def build_heap(data):
    n = len(data)
    for i in range(n//2, -1, -1):
        sift_down(i, n, data)

    return swaps

# wrong answer using while loop instead of recursion
def build_heap2(data):
    swap = []
    for i in range(len(data)-1, 0, -1):
        current_node = i
        prev_node = i // 2 if i % 2 != 0 else i // 2 - 1

        while data[prev_node] > data[current_node] and current_node != 0:
            swap.append((prev_node, current_node))
            data[prev_node], data[current_node] = data[current_node], data[prev_node]
            current_node = prev_node
            prev_node = current_node // 2 if current_node % 2 != 0 else current_node // 2 - 1

    return swap


def main():
    # n = int(input())
    # data = list(map(int, input().split()))
    # assert len(data) == n
    
    while True:
        n = randint(1, 100000)
        data = []
        data2 = []
        for i in range(n):
            data.append(randint(0, 10^9))
        data2 = data.copy()
        
        swaps = build_heap(data)
        swaps2 = build_heap2(data2)
        
        
        if swaps != swaps2:
            print("recursion")
            print(data[0], len(data), len(swaps))
            print("loop:")
            print(data2[0], len(data2), len(swaps2))
            break
        
        else:
            print("success")
    
    swaps = build_heap(data)

    print(len(swaps))
    for i, j in swaps:
        print(i, j)

if __name__ == "__main__":
    main()
Improve this question

2 Answers 2

Reset to default
1

Your build_heap2 implements an idea that is not correct. It starts from the bottom of the tree (correct), but then bubbles values up the tree (wrong), in the upper part of the tree that has not been heapified yet. This is not good. Not only can it report the wrong number of swaps, it will not always deliver a valid heap. For instance, for [3, 1, 2, 4, 0] the result after the swaps is still not a heap, as the value 1 ends up as a child of 3.

The purpose is to build little heaps at the bottom of the tree and after the children of a parent node have been turned into heaps, the value in that parent node is sifted down into either of these child-heaps. This is right, as now the moving value is moving within a subtree that is already heapified. The result is that the parent of these two little heaps is now the root of a valid heap itself. And so at the end of the algorithm, the root will be the root of a valid heap.

So instead of swapping values upwards in the tree, you need to swap downwards (choosing the child with the least value).

Here is the corrected version:

def build_heap(data):
    swap = []
    # We can start at the deepest parent:
    for i in range(len(data) // 2 - 1, -1, -1):
        current_node = i
        
        while True:
            child_node = current_node * 2 + 1
            if child_node >= len(data):
                break
            if child_node + 1 < len(data) and data[child_node + 1] < data[child_node]:
                child_node += 1
            if data[current_node] < data[child_node]:
                break
            # swap the current value DOWN, with the least of both child values
            swap.append((child_node, current_node))
            data[child_node], data[current_node] = data[current_node], data[child_node]
            current_node = child_node
    return swap
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

That's precisely what their first build_heap does, isn't it?
@rici, yes, but in iterative way, which is what the Asker was attempting to do.
1

There are (at least) two ways to build a heap.

The O(N) solution works backwards from the middle of the dataset towards the beginning, ensuring that each successive element is the correct root of the subtree at that point:

def build_heap_down(data):
    n = len(data)
    for subtree in range(n // 2 - 1, -1, -1):
        sift_down(subtree, n, data)

The other solution, which is O(N log N), just adds each element in turn to a successively larger heap:

def build_heap_up(data):
    for new_element in range(1, n):
        sift_up(new_element, data)

Since build_heap_up() is log-linear in the worst case (which I believe is reverse-sorted input), it probably doesn't satisfy the needs of your assignment, which impose a linear bound on the number of swaps. Still, some experimentation is worth doing. Perhaps that's the point of this assignment.

def sift_up(elt, data):
    while elt > 0:
        parent = (elt - 1) // 2
        if data[parent] <= data[elt]: return
        swap(parent, elt, data)
        elt = parent

def sift_down(elt, limit, data):
    while True:
        kid = 2 * elt + 1
        if kid >= limit: return
        if kid + 1 < limit and data[kid + 1] < data[kid]: kid += 1
        if data[elt] <= data[kid]: return
        swap(elt, kid, data)
        elt = kid

The key insight here is that both sift_up and sift_down require that the array they are working with be a heap except for the element being sifted. sift_down works with the array from the sifted element to the end, so doing it correctly on the entire array requires working backwards. sift_up works with the array from the beginning to the sifted element, so the iteration has to work forwards.

Your build_heap does build_heap_down, as far as I can see correctly. Although it uses recursion, it does the same thing as my loop above (and the version from @trincot); recursion at the very end of a function can always be turned into a simple loop using tail call elimination. (Some languages automatically perform this program transformation, but Python isn't one of them.)

Your build_heap2 is an incorrect version of build_heap_up because it works backwards instead of working forwards. That's easy to fix. But don't expect it to produce the same heap, much less the same list of swaps. There are many possible heaps which can be built from a given list of numbers, which is why it's possible to find an O(N) algorithm for build_heap and not for sort.

Improve this answer

4 Comments

thanks for your explanation! To clarify, is there an explanation why the same heap won't be generated for the same given array if build_heap_up or build_heap_down is used? I understand that build_heap is the first step for heap sort. But why does the property that 'many possible heaps can be built from a given list of numbers' lead to O(n) time complexity for build_heap but O(nlg(n)) for sort at best?
V (with N distinct elements) needs to be sorted. There are N! possible rearrangements of V; only one is sorted and we need to find it. We repeatedly compare two elements in V. Each comparison can at best eliminate half of the possibilities. So we need to do at least log2(N!) comparisons in order to reduce the number of possibilities to 1. Using Stirling's approximation for factorial, log2(N!) is O(N log N). That's the minimum number of comparisons needed.
V (with N distinct elements) needs to be turned into a binary heap. It's not quite so simple to figure out how many possible binary heaps of size N there are, but it turns out that there are about N! / exp (N), where e is the ubiquitous constant of Euler, 2.71828... It doesn't matter which possibility we select, and the division by an exponential cancels out the log N term in the number of comparisons needed. So in principle, it's possible that only O(N) comparisons are necessary, and build_heap_down demonstrates that the possibility is real.
@Young42 As for the question, why do build_heap_up and build_heap_down produce different heaps: Why should they produce the same heap? There are so many possible heaps to choose from and the algorithms are completely different; they work on the data elements in opposite orders. If they magically produced the same heap, that would require explanation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.