Skip to content

Instantly share code, notes, and snippets.

@barsv
Last active November 30, 2021 20:15
Show Gist options
  • Save barsv/2620a733d118d7df34f570adc167713e to your computer and use it in GitHub Desktop.
Save barsv/2620a733d118d7df34f570adc167713e to your computer and use it in GitHub Desktop.
Fixed version of the heap implementation from https://www.programiz.com/dsa/heap-data-structure
# Max-Heap data structure in Python
import math
def siftDown(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
siftDown(arr, n, largest)
def siftUp(arr, n, i):
if i <= 0:
return
parent = (i - 1) // 2
if arr[parent] < arr[i]:
arr[i], arr[parent] = arr[parent], arr[i]
siftUp(arr, n, parent)
def insert(array, newNum):
size = len(array)
if size == 0:
array.append(newNum)
else:
array.append(newNum)
siftUp(array, len(array), len(array)-1)
def deleteNode(array, num):
size = len(array)
i = 0
for i in range(0, size):
if num == array[i]:
break
array[i], array[size - 1] = array[size - 1], array[i]
array = array[:size-1]
siftDown(array, len(array), i)
return array
def printHeap(array):
size = len(array)
height = math.ceil(math.log(size, 2))
for h in range(0, height):
start = 2**h
end = 2**(h+1)
print(array[start-1:end-1])
def heapify(array):
size = len(array)
for i in range(size // 2 - 1, -1, -1):
siftDown(array, size, i)
arr = []
insert(arr, 9)
print("Max-Heap array: " + str(arr))
insert(arr, 4)
print("Max-Heap array: " + str(arr))
insert(arr, 5)
print("Max-Heap array: " + str(arr))
insert(arr, 1)
print("Max-Heap array: " + str(arr))
insert(arr, 3)
print("Max-Heap array: " + str(arr))
insert(arr, 2)
print("Max-Heap array: " + str(arr))
insert(arr, 7)
print("Max-Heap array: " + str(arr))
print("printHeap:")
printHeap(arr)
arr = deleteNode(arr, 9)
print("After deleting element 9: " + str(arr))
print("heapify:")
arr = [1,2,3,4,5,7,9]
heapify(arr)
printHeap(arr)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment