#!/usr/bin/python
""" A modeule containing Heap class"""
def getList():
return [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
def getRandomList():
import random
random.seed()
l = []
for i in range(10):
l.append(random.choice(range(10)))
return l
def getLeft(index):
"""Get the index of left child
Args:
index (int), index of current node
Returns:
int, index of the left child
"""
return index*2+1
def getRight(index):
"""Get the index of right child
Args:
index (int), index of current node
Returns:
int, index of the right child
"""
return index*2+2
def maxHeapify(l, index, n):
"""Max heapify the tree
Args:
l (list), a list of objects
i (int), index of current node
n (int), index of the last node in the list
"""
# lg(n)
left = getLeft(index)
right = getRight(index)
largest = index
if left <= n and l[left] > l[index]:
largest = left
if right <= n and l[right] > l[largest]:
largest = right
if largest != index:
l[largest], l[index] = l[index], l[largest]
maxHeapify(l, largest, n)
def buildMaxHeap(l):
# nlg(n)
for i in range(int(len(l)/2 - 1), -1, -1):
maxHeapify(l, i, len(l)-1)
def heapSort(l):
# nlg(n)
buildMaxHeap(l)
print(l)
for i in range(len(l)-1, 0, -1):
l[0], l[i] = l[i], l[0]
maxHeapify(l, 0, i-1)
def main():
l = getList();
print(l)
heapSort(l)
print(l)
l = getRandomList()
print(l)
heapSort(l)
print(l)
if __name__ == '__main__':
main()
