Skip to content

Instantly share code, notes, and snippets.

@RadhikaG
Last active December 13, 2016 13:57
Show Gist options
  • Save RadhikaG/2f627fd74a272f653f92 to your computer and use it in GitHub Desktop.
Save RadhikaG/2f627fd74a272f653f92 to your computer and use it in GitHub Desktop.
A short script to demonstrate the different operations on heaps.
global heap
global currSize
def parent(i): #returns parent index of ith index
return i/2
def left(i): #returns left child of ith index
return 2*i
def right(i): #returns right child of ith index
return (2*i + 1)
def swap(a, b): #to swap a-th and b-th elements in heap
temp = heap[a]
heap[a] = heap[b]
heap[b] = temp
def insert(elem):
global currSize
index = len(heap)
heap.append(elem)
currSize += 1
par = parent(index)
flag = 0
while flag != 1:
if index == 1: #we have reached the root of the heap
flag = 1
elif heap[par] > elem: #if parent index is larger than index of elem, then elem has now been inserted into the right place
flag = 1
else: #swaps the parent and the index itself
swap(par, index)
index = par
par = parent(index)
print heap
def extractMax():
global currSize
if currSize != 0:
maxElem = heap[1]
heap[1] = heap[currSize] #replaces root element with the last element
heap.pop(currSize) #deletes last element present in heap
currSize -= 1 #reduces size of heap
maxHeapify(1)
return maxElem
def maxHeapify(index):
global currSize
lar = index
l = left(index)
r = right(index)
#print heap
#finds the larger child of the index; if larger child exists, swaps it with the index
if l <= currSize and heap[l] > heap[lar]:
lar = l
if r <= currSize and heap[r] > heap[lar]:
lar = r
if lar != index:
swap(index, lar)
maxHeapify(lar)
def buildHeap():
global currSize
for i in range(currSize/2, 0, -1): #third argument in range() shows increment factor, here -1
print heap
maxHeapify(i)
currSize = len(heap)-1
def heapSort():
for i in range(1, len(heap)):
print heap
heap.insert(len(heap)-i, extractMax()) #inserting the greatest element at the back of the array
currSize = len(heap)-1
heap = []
i = 0
s = 'blah'
print "Welcome to heap program. Enter your list below:"
while s != '':
s = raw_input('--> ')
if s != '':
heap.append(int(s))
currSize = len(heap)
heap.insert(0, 0)
print "Building heap..."
buildHeap()
print heap
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment