Im using minheap for solving my question but heap is placing few elements that are larger 1st and i cant understand why

Question

Ok so min heap place small value 1st in heap but in my case 5.xxx is being placed before 3.xxx and i dont know how to solve this issue when im using sort its giving correct answer but i want to do it with heap

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        ratio = [(w / q, q) for w, q in zip(wage, quality)]
        # heapq.heappush(ratio,[(w/q,q) for w,q in zip(wage,quality)])
        heapq.heapify(ratio)
        print(ratio)

output:- [(2.269662921348315, 89), (3.223684210526316, 76), **(5.101694915254237, 59), (3.875, 56)**, (7.538461538461538, 39), (17.115384615384617, 26), (5.5, 86), (6.428571428571429, 14), (138.33333333333334, 3), (13.527777777777779, 36)]

can anyone explain me why 5 is placed before 3 and how can i solve it?

Answer 1

A min heap is a binary heap where each parent is less than either of its children.

When representing a binary heap as an array, we normally use level order traversal:

(Image from https://www.geeksforgeeks.org/binary-heap/).

So, taking your array and drawing it as a heap (and rounding each member to 1dp):

              2.3
          /        \
         /          \
       3.2          5.1
     /     \       /   \
   3.9    7.5   17.1   5.5
  /  \    /
6.4 138 13.5

You can clearly see that the min heap property is satisfied, and that each parent is less than either of its children.

In other words, your expectation that heapifying an array means that it will be sorted is incorrect. A heap is not a strictly sorted data structure.

Take a look at the Heapsort sorting algorithm. In order to sort an array, it first constructs a min heap, and then uses that min heap to construct a sorted array. So it should be clear that constructing a min heap is only one step in the process of sorting.