Skip to content

Instantly share code, notes, and snippets.

@komasaru komasaru/heap_upward.py
Last active Apr 21, 2018

Embed
What would you like to do?
Python script to generate a heap by the upward method.
#! /usr/local/bin/python3.6
"""
Heap generation with the upward method
"""
import random
import sys
import traceback
class Heap:
N = 100 # Number of data
def __init__(self):
self.base = []
for _ in range(self.N):
self.base.append(random.randrange(self.N) + 1)
self.__display(0)
self.heap = [0 for _ in range(self.N + 1)]
def generate(self):
""" Heap generation """
try:
for n in range(1, self.N + 1):
self.heap[n] = self.base[n - 1]
s = n
p = int(s / 2)
while s >= 2 and self.heap[p] > self.heap[s]:
w = self.heap[p]
self.heap[p] = self.heap[s]
self.heap[s] = w
s = p
p = int(s / 2)
self.__display(1)
except Exception as e:
raise
def __display(self, k):
""" Display
:param int k: 0: list of base,
1: list of heap
"""
try:
print("#### ", end="")
if k == 0:
print("Base")
else:
print("Heap")
for i in range(k, self.N + k):
if k == 0:
print("{:5d} ".format(self.base[i]), end="")
else:
print("{:5d} ".format(self.heap[i]), end="")
if (i + 1 - k) % 10 == 0 or i == self.N - 1 + k:
print()
except Exception as e:
raise
if __name__ == '__main__':
try:
obj = Heap()
obj.generate()
except Exception as e:
traceback.print_exc()
sys.exit(1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.