python-Labs/heep.py at master · AmadIrfan/python-Labs · GitHub

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
from math import *


def Left(i):
    return 2*i


def right(i):
    return (2*i)+1


def Parent(i):
    return floor(i/2)


def MaxHeapify(Arr, i):
    l = Left(i)
    r = right(i)
    if l <= Arr.heapSize and Arr[l] < Arr[i]:
        largest = l
    else:
        largest = i

    if r < Arr.heapSize and Arr[r] < Arr[largest]:
        largest = r
    if (largest != i):
        temp = Arr[largest]
        Arr[largest] = Arr[i]
        Arr[i] = temp
    MaxHeapify(Arr, largest)


def Build_Max_Heap(A):
    A.heapSize = A.length
    for i in reversed(range(1, len(A)/2)):
        MaxHeapify(A, i)


def heapSort(A):
    Build_Max_Heap(A)
    for i in reversed(range(2, len(A))):
        A[1], A[i] = A[i], A[1]
        A.heapSize = A.heapSize-1
        MaxHeapify(A, i)


def heap_max_extrect(A):
    if A.heapSize < 1:
        Exception('heep underflow')
    max = A[1]
    A[1] = A[A.heapSize]
    A.heapSize = A.heapSize-1
    MaxHeapify(A, 1)
    return max


def heapIncreaseKey(A, i, key):
    if key < A[i]:
        print('error')
        A[i] = key
        while i > 1 and A[Parent(i)] < A[i]:
            A[i], A[Parent(i)] = A[Parent(i)], A[i]
            i = Parent(i)


def max_heap_insert(A, key):
    A.heapSize = A.heapSize+1
    A[A.heapSize] = -1999999999
    heapIncreaseKey(A, A.heapSize, key)