Heap struct and algorithm

Heap Thoughts

---

Head definition

Heap is a complete binary tree, it can be categorized as two classes: Min-Heap and Max-Heap

Min-Heap is a Binary tree, which parent node always is smaller than its child node.
Max-Heap is a Binary tree, which parent node always is bigger than its child node.

Note: The child tree on the Min-Heap/Max-Heap has same attitude. **

### Data Strut
The simplest way to store such Heap is implicitly stored on a array (vector in C++, List in Java or Python), but For Big data, it should be stored on a link table, this help store the big data on different pages but can be located quickly.
The Left content are based on Max-Heap for example.

### Usage

• Priority Queue
• Sort
• so on

  As root node of Max-heap stores the max value in the whole heap data. when a data is pushed on  
  the heap, it will be adjusted to meet the Max-heap attitude. when a program want to get the  
  priority data, the heap just need pop the root node and re-adjust the heap.
  

Source code

import os

class Heap(object):
    def __init__(self, array, heap='min'):
        self.__array = array
        self.__type = True
        if heap == 'min':
            self.__type = False;

        self.__build()

    def __left_pos(self, root):
        return (root + 1) * 2 - 1

    def __right_pos(self, root):
        return (root + 1) * 2

    def __root_pos(self, child):
        return int((child - 1) /2)

    def __leaf(self, pos):
        return pos < len(self.__array) and pos >= 0

    def __swap(self, pos1, pos2):
        if self.__leaf(pos1) and self.__leaf(pos2) and pos1 != pos2:
            tmp = self.__array[pos1]
            self.__array[pos1] = self.__array[pos2]
            self.__array[pos2] = tmp

    '''
    ## this method adjust the tree on the original array ###
    build the heap from down to up to find the max value on a child tree,
    when the tree exchange the data, it need to recall this function to re-adjust the down tree  from up to down
    '''
    def __headify(self, root):
        left = self.__left_pos(root)
        right = self.__right_pos(root)
        largest = root

        if self.__leaf(left) and self.__array[left] > self.__array[largest]:
            largest = left

        if self.__leaf(right) and self.__array[right] > self.__array[largest]:
            largest = right

        self.__swap(root, largest)
        if root != largest:
            self.__headify(largest)


    def __build(self):
        if len(self.__array) < 2:
            return

        root = int(len(self.__array)/2) - 1
        while not root < 0:
            self.__headify(root)
            root -= 1

    def build_push(self, arr):
        self.__array = []
        for item in arr:
            self.push(item)

    '''
    ## to push a node to the heap need append the node on the array tail, and recursively exchange with its parent node util it litter than its parent node.

    it is called bubble up   .。oO
    '''
    def push(self, x):
        self.__array.append(x)
        child = len(self.__array) - 1

        while True:
            root = self.__root_pos(child)
            if root >= 0 and self.__array[child] > self.__array[root]:
                self.__swap(child, root)
                child = root
                continue
            break

    '''
    ## to pop the heap means to pop the root node ##
    directly pop the root node and move the tail data to the head slot.
    and adjust the data from up to down

    it is called bubble down Oo。.
    '''
    def pop(self):
        tmp = self.__array[0]
        self.__array[0] = self.__array[-1]
        del self.__array[-1]
        root = 0
        self.__headify(root)
        return tmp

    def print_heap(self):
        print self.__array

Test

array = [15, 45, 12, 34, 17, 54, 23, 0, 2, 32, 57,89]
heap = Heap(array)
heap.print_heap()
heap.build_push(array)
print "push build:"
heap.print_heap()
heap.pop()
heap.pop()
heap.print_heap()