Skip to content

Instantly share code, notes, and snippets.

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

Embed
What would you like to do?
Python script to generate a heap by the downward method.
#! /usr/local/bin/python3.6
"""
Heap generation with the downward method
"""
import random
import sys
class Heap:
N = 100 # Number of data
def __init__(self):
self.heap = [0]
for _ in range(self.N):
self.heap.append(random.randrange(self.N) + 1)
self.__display(0)
def generate(self):
""" Heap generation """
try:
n = self.N
for i in range(int(n / 2), 0, -1):
p = i
s = 2 * p
while s <= n:
if s < n and self.heap[s + 1] < self.heap[s]:
s += 1
if self.heap[p] <= self.heap[s]:
break
self.__swap(p, s)
p = s
s = 2 * p
self.__display(1)
except Exception as e:
raise
def __swap(self, a, b):
""" Swapping
:param int a: index of heap list
:param int b: index of heap list
"""
try:
w = self.heap[a]
self.heap[a] = self.heap[b]
self.heap[b] = w
except Exception as e:
raise
def __display(self, k):
""" Display
:param int k: 0: list of tree,
1: list of heap
"""
try:
print("#### ", end="")
if k == 0:
print("Tree")
else:
print("Heap")
for i in range(1, self.N + 1):
print("{:5d} ".format(self.heap[i]), end="")
if i % 10 == 0 or i == self.N:
print()
except Exception as e:
raise
if __name__ == '__main__':
try:
obj = Heap()
obj.generate()
except Exception as e:
print("EXCEPTION!", e.args, file=sys.stderr)
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.