Heap code, don't understand

Currently doing the exercise on min-heaps and we are trying to switch parent and child value if parent s bigger. I : don’t understand the before last sentence: idx = self.parent_idx(idx) Thank you in advance!

def heapify_up(self):

print("Heapifying up")

idx = self.count

while self.parent_idx(idx) > 0:

  child = self.heap_list[idx]

  parent = self.heap_list[self.parent_idx(idx)]

  if parent > child:

    print("swapping {0} with {1}".format(parent, child))

    self.heap_list[idx] = parent

    self.heap_list[self.parent_idx(idx)] = child

  idx = self.parent_idx(idx)

print("Heap Restored {0}".format(self.heap_list))

Hi,

I find that drawing out the process of the state of the heap helps out. (on paper)
If you want to get confirmation in code you could do more f strings.

@object0210195723 To be a little clearer: Data structures are not something that are easily digestible in one sitting, they are structures with sometimes intricate components. It’s like looking at the inside of an analog watch and trying to grasp everything in one go.

Break it apart and build it it from the ground up. What can the first component do (as opposed to what it does in its final form), what does the 2nd comp, 3rd, etc.
This will come in handy because it’ll translate to other structures as well.

2 Likes

Same exercise but a different part I don’t understand why it has to be self.heap_list[1] = self.heap_list[self.count]
instead of self.heap_list[1] = self.heap_list[-1]

def retrieve_min(self):

if self.count == 0: #first element

  print("No items in heap")

  return None

else:

  min = self.heap_list[1]

  print("Removing: {0} from {1}".format(min, self.heap_list))

  self.heap_list[1] = self.heap_list[self.count]

  self.heap_list.pop()

  self.count -= 1

  print("Last element moved to first:{0}".format(self.heap_list))

  return min

Both of them will result in the same thing. self.heap_list[self.count] and self.heap_list[-1] will both index into the last element of the heap_list list.

2 Likes