2
\$\begingroup\$

Created a max heap using a Python list as the base storage. The heap starts at index 1.

Here is the heap:

class Heap:
  def __init__(self):
    # storage starts with an unused 0 to make 
    # integer division simpler later on
    self.storage = [0]
    self.size = 0

  def insert(self, value):
    self.storage.append(value)
    self.size += 1
    self._bubble_up(self.size)


  def delete(self):
    self.storage[1], self.storage[-1] = self.storage[-1], self.storage[1]
    deleted_value = self.storage.pop(-1)
    self.size -= 1
    self._sift_down_(1)
    return deleted_value

  def get_max(self):
    return self.storage[1]

  def get_size(self):
    return self.size

  def _bubble_up(self, index):
      # my two part base case for recursion: 
      # if parent is greater than child or if index less than or equal to one
      if self.storage[index] < self.storage[index//2] or index <= 1:
          return
      else:
          # swap the parent/child values
          self.storage[index], self.storage[index//2] = self.storage[index//2], self.storage[index]
          # recursive call
          return self._bubble_up(index//2)


  def _sift_down_(self, index):
    left_child = index * 2
    right_child = (index * 2) + 1
    if left_child > self.size:
      return
    if right_child <= self.size:
        if self.storage[index] < self.storage[left_child] or self.storage[index] < self.storage[right_child]:
            largest_child = right_child if (self.storage[right_child] > self.storage[left_child]) else left_child
            self.storage[index], self.storage[largest_child] = self.storage[largest_child], self.storage[index]
            return self._sift_down_(largest_child)
        else:
          return              
    else:
      if self.storage[index] < self.storage[left_child]:
        self.storage[index], self.storage[left_child] = self.storage[left_child], self.storage[index]
        return self._sift_down_(left_child)
      else:
        return

Produces the correct output when used:

heap = Heap()

heap.insert(40)
heap.insert(18)
heap.insert(20)
heap.insert(15)
heap.insert(13)
heap.insert(9)
heap.insert(19)
heap.insert(1)
heap.insert(3)
heap.insert(8)

print(heap.storage)

heap.delete()
print("heap after delete(): ", heap.storage)
print(heap.get_size())

Outputs:

[0, 40, 18, 20, 15, 13, 9, 19, 1, 3, 8]
heap after delete():  [0, 20, 18, 19, 15, 13, 9, 8, 1, 3]
9

Seeking any and all feedback; missing edge cases, logical flaws, and general improvement tips.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.