-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBinaryHeap.py
125 lines (104 loc) · 4.07 KB
/
BinaryHeap.py
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
# Created by Elshad Karimov
# Copyright © 2021 AppMillers. All rights reserved.
class Heap:
def __init__(self, size):
self.customList = (size+1) * [None]
self.heapSize = 0
self.maxSize = size + 1
def peekofHeap(rootNode):
if not rootNode:
return
else:
return rootNode.customList[1]
def sizeofHeap(rootNode):
if not rootNode:
return
else:
return rootNode.heapSize
def levelOrderTraversal(rootNode):
if not rootNode:
return
else:
for i in range(1, rootNode.heapSize+1):
print(rootNode.customList[i])
def heapifyTreeInsert(rootNode, index, heapType):
parentIndex = int(index/2)
if index <= 1:
return
if heapType == "Min":
if rootNode.customList[index] < rootNode.customList[parentIndex]:
temp = rootNode.customList[index]
rootNode.customList[index] = rootNode.customList[parentIndex]
rootNode.customList[parentIndex] = temp
heapifyTreeInsert(rootNode, parentIndex, heapType)
elif heapType == "Max":
if rootNode.customList[index] > rootNode.customList[parentIndex]:
temp = rootNode.customList[index]
rootNode.customList[index] = rootNode.customList[parentIndex]
rootNode.customList[parentIndex] = temp
heapifyTreeInsert(rootNode, parentIndex, heapType)
def inserNode(rootNode, nodeValue, heapType):
if rootNode.heapSize + 1 == rootNode.maxSize:
return "The Binary Heap is Full"
rootNode.customList[rootNode.heapSize + 1] = nodeValue
rootNode.heapSize += 1
heapifyTreeInsert(rootNode, rootNode.heapSize, heapType)
return "The value has been successfully inserted"
def heapifyTreeExtract(rootNode, index, heapType):
leftIndex = index * 2
rightIndex = index * 2 + 1
swapChild = 0
if rootNode.heapSize < leftIndex:
return
elif rootNode.heapSize == leftIndex:
if heapType == "Min":
if rootNode.customList[index] > rootNode.customList[leftIndex]:
temp = rootNode.customList[index]
rootNode.customList[index] = rootNode.customList[leftIndex]
rootNode.customList[leftIndex] = temp
return
else:
if rootNode.customList[index] < rootNode.customList[leftIndex]:
temp = rootNode.customList[index]
rootNode.customList[index] = rootNode.customList[leftIndex]
rootNode.customList[leftIndex] = temp
return
else:
if heapType == "Min":
if rootNode.customList[leftIndex] < rootNode.customList[rightIndex]:
swapChild = leftIndex
else:
swapChild = rightIndex
if rootNode.customList[index] > rootNode.customList[swapChild]:
temp = rootNode.customList[index]
rootNode.customList[index] = rootNode.customList[swapChild]
rootNode.customList[swapChild] = temp
else:
if rootNode.customList[leftIndex] > rootNode.customList[rightIndex]:
swapChild = leftIndex
else:
swapChild = rightIndex
if rootNode.customList[index] < rootNode.customList[swapChild]:
temp = rootNode.customList[index]
rootNode.customList[index] = rootNode.customList[swapChild]
rootNode.customList[swapChild] = temp
heapifyTreeExtract(rootNode, swapChild, heapType)
def extractNode(rootNode, heapType):
if rootNode.heapSize == 0:
return
else:
extractedNode = rootNode.customList[1]
rootNode.customList[1] = rootNode.customList[rootNode.heapSize]
rootNode.customList[rootNode.heapSize] = None
rootNode.heapSize -= 1
heapifyTreeExtract(rootNode, 1, heapType)
return extractedNode
def deleteEntireBP(rootNode):
rootNode.customList = None
newHeap = Heap(5)
inserNode(newHeap, 4, "Max")
inserNode(newHeap, 5, "Max")
inserNode(newHeap, 2, "Max")
inserNode(newHeap, 1, "Max")
deleteEntireBP(newHeap)
levelOrderTraversal(newHeap)