Python: Data structure (1)

Abstract: heap using the module heapq

construct a minheap or maxheap, and index elements of a heap, and construct a heap with turple.

The script:
# -*- coding: utf-8 -*-
"""
Created on Fri Jul 10 10:07:47 2015

@author: yuan
"""

import heapq
import math
import numpy as np

class tree:
    def __init__(self, arr):
        self.arr=arr
        self.nodes_num=len(arr)
        self.tree_height=math.ceil(math.log(self.nodes_num,2))
        print 'Tree height: ', self.tree_height
       
    def min_tree(self):
        heap=list(self.arr)       
        heapq.heapify(heap)
        print 'the minimum tree is', heap
        return heap


       

#main program
data=[19,9,4,1,19,10,11,20,1,100,102,56]

#read list as data
min_heap=list(data)
heapq.heapify(min_heap)
print "the tree is ",  min_heap

#add a node
heapq.heappush(min_heap,3)
print min_heap

#remove the smallest one
s=heapq.heappop(min_heap)
print s, min_heap

#remove the smallest one and add a new one
s=heapq.heappushpop(min_heap, 2)
print s, min_heap


#heap of list and turple combined
d=[(4,'a'), (9,'c'),(7,'b'),(10,'d'),(14,'e'),(40,'f'), (4,'g'),(90,'h')]
heap=[]
for item in d:
    pos=item[0]
    name=item[1]
    heapq.heappush(heap, (pos,int(pos+pos*0.7),name) )
print 'Dict heap:', heap

node=heapq.heappop(heap)
print 'reserved Dict heap:', heap
print 'smallest node by turple', node


#index heap
print "\nIndex of heap:", heap
n=len(heap)
print 'Nodes of the tree:', n
h=int(math.ceil(math.log(len(heap),2)))
print "height of the tree:",h
i=3
print 'The', i,'th of the heap:', heap[i-1]
print 'node', i, 'is in the layer', int(math.ceil(math.log(i,2)))
#father node of node i
f=int(i/2)
print 'father node', f, heap[f-1]
#left child of node i
c=2*i
print 'left child:', c, heap[c-1]
#left child of node i
c=2*i+1
print 'right child:', c, heap[c-1]


#construct maxheap
maxheap=[]
for item in d:
    pos=item[0]
    name=item[1]
    heapq.heappush(maxheap, (-pos,-int(pos+pos*0.7),name) )
print 'Dict heap:', maxheap