# class Node:
# def __init__(self, value,count) -> None:
# self.value=value
# self.count=count
from ta import build_heap
def heapify(heap, heapsize, idx):
if idx<0 or idx>=heapsize:
return
leftnode = 2*idx+1
rightnode = 2*idx+2
max = idx
if leftnode<heapsize and heap[leftnode]>heap[max]:
max = leftnode
if rightnode<heapsize and heap[rightnode]>heap[max]:
max = rightnode
if max != idx:
if max==leftnode:
heap[idx], heap[max] = heap[max], heap[idx]
heapify(heap, heapsize, leftnode)
else:
heap[idx], heap[max] = heap[max], heap[idx]
heapify(heap, heapsize, rightnode)
return
def make_heap(heap, heapsize):
lastnode = len(heap)-1
parent_lastnode = (lastnode-1)//2
for i in range(parent_lastnode, -1,-1):
heapify(heap, heapsize, i)
return
def heap_sort(heap):
make_heap(heap, len(heap))
lastnode = len(heap)-1
for i in range(lastnode, -1, -1):
heap[i], heap[0] = heap[0], heap[i]
heapify(heap, i-1, 0)
return
# data=[8,10,6,7,9,1,100]
data=[2,2,3,2,1,1,1,2,2,3]
# heapify(data,len(data),0)
# make_heap(data)
heap_sort(data)
print(data)