from __future__ import absolute_import
from __future__ import division
from __future__ import print_function

import numpy as np


def parent(i):
    return i // 2

def left(i):
    return 2 * i

def right(i):
    return 2 * i + 1


class MinPriorityQueue(object):
    """Min Priority Queue."""
    def __init__(self):
        self.heap_ls = [[0, 0]]
        self.heap_size = 0

    def show(self):
        print(self.heap_ls)

    def min_heapify(self, i):
        l = left(i)
        r = right(i)
        if l <= self.heap_size and self.heap_ls[l][0] < self.heap_ls[i][0]:
            min_i = l
        else:
            min_i = i
        if r <= self.heap_size and self.heap_ls[r][0] < self.heap_ls[min_i][0]:
            min_i = r
        if min_i != i:
            self.heap_ls[i], self.heap_ls[min_i] = (
                self.heap_ls[min_i], self.heap_ls[i])
            self.min_heapify(min_i)

    def find_min(self):
        return self.heap_ls[1]

    def extract_min(self):
        print('Extract min:')
        if self.heap_size < 1:
            raise ValueError('Heap underflow.')
        minimum = self.heap_ls[1]
        # self.heap_ls[1] = self.heap_ls.pop()
        last = self.heap_ls.pop()
        print('After extraction, self.heap_ls: {}'.format(self.heap_ls))
        self.heap_ls.insert(1, last)
        print('After insertion: self.heap_ls: {}'.format(self.heap_ls))
        self.heap_size -= 1
        print('heap size: {}'.format(self.heap_size))
        self.min_heapify(1)
        return minimum

    def decrease_key(self, i, key):
        print('i: {}'.format(i))
        print('key: {}'.format(key))
        print('self.heap_ls[{}][0]: {}'.format(i, self.heap_ls[i][0]))

        if key > self.heap_ls[i][0]:
            raise ValueError('New key is larger than current key.')
        self.heap_ls[i][0] = key
        while i > 1 and self.heap_ls[parent(i)][0] > self.heap_ls[i][0]:
            self.heap_ls[i], self.heap_ls[parent(i)] = (
                self.heap_ls[parent(i)], self.heap_ls[i])
            i = parent(i)

    def insert(self, new_node):
        key, item = new_node
        print('Heap_size: {}'.format(self.heap_size))        
        
        self.heap_ls.append([np.inf, item])
        print('Insert to heap_ls: {}'.format(self.heap_ls))

        self.heap_size += 1
        print('After insertion: heap_size: {}'.format(self.heap_size))

        self.decrease_key(self.heap_size, key)


def main():
    min_pq = MinPriorityQueue()

    print('Binary heap tuple with [5, a], [7, c], [3, b], [1, e]:')
    min_pq.insert([5, 'a'])
    min_pq.insert([7, 'c'])
    min_pq.insert([3, 'b'])
    min_pq.insert([1, 'd'])
    min_pq.show()

    print('Decrease key 7 at position 4 to 2.')
    min_pq.decrease_key(4, 2)
    min_pq.show()

    print('Find min key:')
    print(min_pq.find_min())

    print('Extract min key:')
    _min = min_pq.extract_min()
    print(_min)
    print('The remaining:')
    min_pq.show()


if __name__ == '__main__':
    main()

@@ -1133,25 +1133,12 @@
     
-# self.heap_ls%5B1%5D
+last
  = s
@@ -1155,38 +1155,34 @@
 s.pop()%0A        
-last =
+if
  self.heap_ls.po
@@ -1180,88 +1180,54 @@
 eap_
-ls.pop()%0A        print('After extraction, self.heap_ls: %7B%7D'.format(self.heap_ls)
+size %3C 1:%0A            self.heap_ls.append(last
 )%0A  
@@ -1236,420 +1236,164 @@
     
-s
 el
-f.heap_ls.insert(1, last)%0A        print('After insertion: self.heap_ls: %7B%7D'.format(self.heap_ls))%0A        self.heap_size -= 1%0A        print('heap size: %7B%7D'.format(self.heap_size))%0A        self.min_heapify(1)%0A        return minimum%0A%0A    def decrease_key(self, i, key):%0A        print('i: %7B%7D'.format(i))%0A        print('key: %7B%7D'.format(key))%0A        print('self.heap_ls%5B%7B%7D%5D%5B0%5D: %7B%7D'.format(i, self.heap_ls%5Bi%5D%5B0%5D))%0A
+se:%0A            self.heap_ls%5B1%5D = last%0A        self.heap_size -= 1%0A        self.min_heapify(1)%0A        return minimum%0A%0A    def decrease_key(self, i, key):
 %0A   
@@ -1806,284 +1806,88 @@
 node
-%0A        print('Heap_size: %7B%7D'.format(self.heap_size))        %0A        %0A        self.heap_ls.append(%5Bnp.inf, item%5D)%0A        print('Insert to heap_ls: %7B%7D'.format(self.heap_ls))%0A%0A        self.heap_size += 1%0A        print('After insertion: heap_size: %7B%7D'.format(self.heap_size))%0A
+        %0A        self.heap_ls.append(%5Bnp.inf, item%5D)%0A        self.heap_size += 1
 %0A   
@@ -2406,13 +2406,33 @@
 int(
+'- Min: %7B%7D'.format(
 _min)
+)
 %0A   
@@ -2439,16 +2439,18 @@
  print('
+- 
 The rema

Revise extract_min()'s pop & replace/insert at pos 1