Im trying trying to build a binary heap by passing it an array of ints. I wanted to know if I should build a class BinaryTree first and then a Heap class in order to implement a binary heap or should I build a single binary heap class? im confused.. thanks!

What language is this?– Mike ChristensenFeb 18 '14 at 19:36

@MikeChristensen its in Java– user3324991Feb 18 '14 at 19:41

@user3324991 Binary Trees can be represented by a simple array. There is no need for an explicit implementation of a Binary Tree. See my answer below.– Marsellus WallaceFeb 18 '14 at 20:01

@Gevorg Thank you I got it now and those links were helpful!– user3324991Feb 18 '14 at 20:09
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.
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 buildheap 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.
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
#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())


1