Array based MinHeap

Question

I am trying to implement a function that turns a list into a MinHeap. I cannot see where I am going wrong.

def min_heapify(nums):
    n = len(nums) - 1
    i = n // 2  # last parent

    while i >= 1:
        k = i
        v = nums[k]
        min_heap = False
        while not min_heap and 2 * k <= n:
            j = 2 * k
            if j + 1 <= n:
                if nums[j + 1] < nums[j]:
                    j += 1
            if nums[k] < nums[j]:
                min_heap = True
            else:
                nums[k] = nums[j]
                k = j
        nums[k] = v
        i -= 1

Example Input:

a_list = [0, 5, 2, 3, 4]
min_heapify(a_list)

Output (the 4 is incorrect):

print("Min Heapify", a_list)  # Min Heapify [0, 2, 5, 3, 4]

Both the 3 and the 4 are incorrect, no? Looks like the 3 and the 5 need swapping? — Mad Physicist
– Mad Physicist, Commented May 9, 2018 at 2:06
That is a correctly sorted min-heap. The children of 0 are 2 and 5, which are greater than 0. The children of 2 are 3 and 4, which again are greater than the parent. The min-node is at the root, 0. The children of a node at position n in the array are at 2n+1 and 2n+2. — TWReever
– TWReever, Commented May 9, 2018 at 2:17
@TWReever 0 is used as a placeholder for the 0th index, since for an array implementation you need this as 2n is 0. — Wizard
– Wizard, Commented May 9, 2018 at 2:23
@Wizard there are actually two ways to represent a heap as an array. A 0-based approach where the children of n are located at 2n+1 and 2n+2 and a 1-based approach, as you stated with children at 2n and 2n+1. — TWReever
– TWReever, Commented May 9, 2018 at 2:33
The simplest way fix to your code is to change the line if nums[k] < nums[j] to if v < nums[j]. If you do that, there's no need to swap nums[j] and nums[k] as suggested in the accepted answer. — Jim Mischel
– Jim Mischel, Commented May 9, 2018 at 3:29

Mark · Accepted Answer · 2018-05-09 02:41:52Z

1

I think you should be swaping num[j] and num[k], where you are just assigning nums[k] = nums[j]:

def min_heapify(nums):
    n = len(nums) - 1
    i = n // 2  # last parent

    while i >= 1:
        k = i
        v = nums[k]
        min_heap = False
        while not min_heap and 2 * k <= n:
            j = 2 * k
            if j + 1 <= n:
                if nums[j + 1] < nums[j]:
                    j += 1
            if nums[k] < nums[j]:
                min_heap = True
            else:
                # HERE: Need to swap num[j] and num[k]
                [nums[j], nums[k]] = [nums[k], nums[j]]
                k = j
        nums[k] = v
        i -= 1

a_list = [0, 11, 5, 2, 3, 4, 7, 17, 6, 1]
min_heapify(a_list)
print(a_list)

# prints: [0, 1, 3, 2, 5, 4, 7, 17, 6, 11]

answered May 9, 2018 at 2:41

Mark

92.7k8 gold badges116 silver badges156 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Array based MinHeap

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related