T6 Heap pop

var datasets = [
  {arg: [0, 1, 2, 3], out: [[1, 3, 2], 0]},
  {arg: [0, 1, 2, 3, 4, 5, 6, 7], out: [[1, 3, 2, 7, 4, 5, 6], 0]},
  {arg: [5, 8, 5, 9, 8, 6, 7], out: [[5, 8, 6, 9, 8, 7], 5]},
  {arg: [2, 4, 5, 4, 6, 4, 5, 8, 5, 9, 8, 6, 7, 5, 8], out: [[4, 4, 5, 5, 6, 4, 5, 8, 8, 9, 8, 6, 7, 5], 2]},
  {arg: [1], out: [[], 1]}
]
var names = ['heap'];

Halda je datová struktura, kde každý prvek (kromě kořenového) má jednoho rodiče, a rodič je vždycky menší nebo stejný než všichni jeho potomci. Binární halda je halda, kde každý prvek má nejvýše dvě děti.

Binární halda je elegantní, protože se dá reprezentovat v poli. Prvek na pozici p má děti na pozicích 2*p+1 a 2*p+2. Rodičem prvku na pozici p je prvek na pozici (p-1)//2. Tyhle výpočty už jsou v zadání hotové.

Vaším úkolem je dopsat funkci heappop(heap), která odebere prvek s nejmenší hodnotou z haldy a vrátí ho. Prvek s nejmenší hodnotou bude zaručeně na pozici 0, a na jeho místo vzápětí přesuneme poslední prvek z haldy. Tím se poruší podmínka haldy, že potomci jsou vždy větší než rodič. Vaším úkolem je tuto podmínku obnovit.

Funkce main(heap) pak vrátí haldy po odebrání prvku a samotný odebraný prvek.

def heappop(heap):
  result = heap[0]
  last_item = heap.pop()
  if heap:
    heap[0] = last_item
  p = 0
  # na tomhle místě je potřeba zařídit, aby platilo pro všechna p:
  # heap[left_child(p)] >= heap[p] and heap[right_child(p)] >= heap[p]
  # příkaz p=0 napovídá, že vlastně stačí opravit prvek na začátku haldy
  return result

def main(heap):
  # na téhle funkci nemusíte nic měnit
  item = heappop(heap)
  return heap, item

def heappush(heap, item):
  # tuhle funkci nebudeme ani potřebovat, píšu ji jen na ukázku
  heap.append(item)
  p = len(heap) - 1
  while heap[parent(p)] > heap[p]:
    swap(heap, p, parent(p))
    p = parent(p)

def parent(pos):
  return (pos - 1) // 2

def left_child(pos):
  return pos * 2 + 1

def right_child(pos):
  return pos * 2 + 2

def swap(heap, a, b):
  heap[a], heap[b] = heap[b], heap[a]