Sunbelt Computer Software

PL/B Language Development and Support

algorithms-python/data_structures/Heap/heap.py at master · alberane/algorithms-python · GitHub

90 lines (75 loc) · 1.72 KB

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

#!/usr/bin/python

from __future__ import print_function, division

try:

raw_input # Python 2

except NameError:

raw_input = input # Python 3

class Heap:

def __init__(self):

self.h = []

self.currsize = 0

def leftChild(self,i):

if 2*i+1 < self.currsize:

return 2*i+1

return None

def rightChild(self,i):

if 2*i+2 < self.currsize:

return 2*i+2

return None

def maxHeapify(self,node):

if node < self.currsize:

m = node

lc = self.leftChild(node)

rc = self.rightChild(node)

if lc is not None and self.h[lc] > self.h[m]:

m = lc

if rc is not None and self.h[rc] > self.h[m]:

m = rc

if m!=node:

temp = self.h[node]

self.h[node] = self.h[m]

self.h[m] = temp

self.maxHeapify(m)

def buildHeap(self,a):

self.currsize = len(a)

self.h = list(a)

for i in range(self.currsize/2,-1,-1):

self.maxHeapify(i)

def getMax(self):

if self.currsize >= 1:

me = self.h[0]

temp = self.h[0]

self.h[0] = self.h[self.currsize-1]

self.h[self.currsize-1] = temp

self.currsize -= 1

self.maxHeapify(0)

return me

return None

def heapSort(self):

size = self.currsize

while self.currsize-1 >= 0:

temp = self.h[0]

self.h[0] = self.h[self.currsize-1]

self.h[self.currsize-1] = temp

self.currsize -= 1

self.maxHeapify(0)

self.currsize = size

def insert(self,data):

self.h.append(data)

curr = self.currsize

self.currsize+=1

while self.h[curr] > self.h[curr/2]:

temp = self.h[curr/2]

self.h[curr/2] = self.h[curr]

self.h[curr] = temp

curr = curr/2

def display(self):

print(self.h)

def main():

l = list(map(int, raw_input().split()))

h = Heap()

h.buildHeap(l)

h.heapSort()

h.display()

if __name__=='__main__':

main()