Building a binary heap

Question 1

A binary heap is a special kind of a binary tree. The heap property should be maintained.

A refresher from Wikipedia: If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. Either the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node (this kind of heap is called max heap) or the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node (min heap).

Depending on your implementation, there will also be some rules about the heap's completeness.

The binary tree does not necessarily have the Binary Search Tree property.

So in other words, simply implement the binary heap as a tree with special features as discussed.

Question 2

A Binary Heap can be represented and stored by simply using an array. There is no need to build/implement a Binary Tree first.

Take a look at the following link about how to represent a binary heap as an array: http://www.cse.hut.fi/en/research/SVG/TRAKLA2/tutorials/heap_tutorial/taulukkona.html

Make sure to understand the Parent(i), Left(i), and Right(i) notions. Also, take a look at the build-heap function to build a heap from an unsorted array: http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap

You start from the first non leaf node in the tree and you invoke heapify all the way up till the root.

Question 3

Here's an example in python that builds a binary heap inside an array.

def add_data(heap, data):
  for i in range(0, len(data)):
    item = data[i]
    insert(heap, item)
  if not is_heap_ordered(heap):
    raise Exception("explode!")

def insert(heap, x):
  heap.append(x)
  swim(heap, len(heap) - 1)

def swim(heap, k):
  parent = k / 2
  while (k > 1) and (heap[parent] < heap[k]):
    exchange(heap, k, parent)
    k = parent
    parent = k / 2

def is_heap_ordered(heap):
  # heap property:  parent is >= children
  limit = len(heap)
  for k in range(1, limit):
    if ((2 * k) > limit - 1) or (((2 * k) + 1) > limit - 1):
      break
    node = heap[k]
    parent = heap[k / 2]
    if k / 2 < 1:  # root node
      parent = node
    childl = heap[2 * k]
    childr = heap[(2 * k) + 1]
    if childl > parent or childr > parent:
      print "heap violated"
      return False
  return True

def exchange(array, i, j):
  temp = array[i]
  array[i] = array[j]
  array[j] = temp

heap = []
input = list("ABCDEF")
random.shuffle(input)
add_data(heap, input)

The first element of the array is not used, this makes the math a little simpler.

The child of each node at position k is located at 2k and 2k+1 The parent of each node is at position k/2

The algorithm is: append an element to the end of the array, then call swim for that element until it is in its proper heap position (heap obeys the 'heap property'). The heap property is that each parent is >= its children.

Here's an animation of the algorithm working

Question 4

#Binary Heap with all the common operations
"""This Code will generate Min Binary Heap with all action that we can perform on Binary Heap. The Formula i have taken is in array 0'th position will be None, Will start from 1'st Position. So root will be at 1 ant left will be at 2x(2) right will be 2x+1(3) Position. """
    class MinHeap():
        """ Min Heap:-Node values will always be lees than the left and right child """
        def __init__(self):
            #Creating a Array to push heap values
            self.heap_list=[None]
            
        def push_element(self,value):
            self.heap_list.append(value)
        #Getting right child from postion 2x
        def get_left_child(self,index):
            for i in range(len(self.heap_list)):
                if i==2*index:
                    return self.heap_list[2*index]
            return 999
        #Getting right child from postion 2x+1
        def get_right_child(self,index):
            for i in range(len(self.heap_list)):
                if i==2*index+1:
                    return self.heap_list[2*index+1]
            return 999
        # I have considered a logic node if node will on x index then left child woul bw at 2*x and right child will be at 2*x+1 postion in array
        def re_construct_heap(self):
            for i in range(1,(len(self.heap_list)//2)+1):
                left_child=self.get_left_child(i)
                right_child=self.get_right_child(i)
                if self.heap_list[i]>left_child :
                    v_parent=self.heap_list[i]
                    self.heap_list[i]=left_child
                    self.heap_list[2*i]=v_parent
                elif self.heap_list[i]>right_child:
                    v_parent=self.heap_list[i]
                    self.heap_list[i]=right_child
                    self.heap_list[2*i+1]=v_parent
        #Re cunstructing heap till the heap property satisfies
        def build_min_heap(self):
          for i in range(len(self.heap_list)//2, 0, -1):
            self.re_construct_heap()
        #Deleing a root node and trying to rebuild Min Heap with heap property
        def delte_node_heap(self,value):
            if self.heap_list[1]==value:
                self.heap_list[1]=self.heap_list[-1]
                self.heap_list.pop(-1)
                self.build_min_heap()
        #Min Value of Heap
        def min_value(self):
            return self.heap_list[1]
        #Max Value of Heap
        def max_value(self):
            return self.heap_list[-1]
        #size of heap
        def size_of_heap(self):
            return len(self.heap_list)
        #Printin Heap Values
        def print_min_heap(self):
            for i in self.heap_list:
                print(i,end='->')
    
    min_heap_obj=MinHeap()
    min_heap_obj.push_element(3)
    min_heap_obj.push_element(5)
    min_heap_obj.push_element(8)
    min_heap_obj.push_element(17)
    min_heap_obj.push_element(19)
    min_heap_obj.push_element(36)
    min_heap_obj.push_element(40)
    min_heap_obj.push_element(25)
    min_heap_obj.push_element(100)
    #insert a node less than root node
    #min_heap_obj.push_element(1)
    #re structuring heap with heap property
    min_heap_obj.build_min_heap()
    #deleting a root node
    min_heap_obj.delte_node_heap(3)
    #re structuring heap with heap property
    min_heap_obj.build_min_heap()
    #printing heap values
    min_heap_obj.print_min_heap()
    print('\n')
    print(min_heap_obj.min_value(),min_heap_obj.max_value(),min_heap_obj.size_of_heap())