Data-Structure/Heap.cpp at main · MKamel2610/Data-Structure · 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
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
#include <iostream>
#include <vector>

using namespace std;

int left(int i) {
    return 2 * i + 1;
}

int right(int i) {
    return 2 * i + 2;
}

int parent(int i) {
    return (i - 1) / 2;
}

template< typename dataType >
void maxHeapify(vector< dataType > &a, int i, int n) { // log(n)
    int largest = i;
    if(left(i) <= n && a[left(i)] > a[largest]) {
        largest = left(i);
    }
    if(right(i) <= n && a[right(i)] > a[largest]) {
        largest = right(i);
    }
    if(largest != i) {
        swap(a[i], a[largest]);
        maxHeapify(a, largest, n);
    }
}

template< typename dataType >
void buildMaxHeap(vector< dataType > &a) { // n log(n) -> n
    int n = int(a.size());
    for(int i = n / 2; i >= 0; i--) { // i = n / 2
        maxHeapify(a, i, n - 1);
    }
}

template< typename dataType >
void heapSort(vector< dataType > &a) { // n log(n)
    buildMaxHeap(a);
    int n = int(a.size());
    for(int i = n - 1; i >= 1; i--) { // i = n / 2
        swap(a[0], a[i]);
        maxHeapify(a, 0, i - 1);
    }
}


template< typename dataType >
dataType heapMaximum(vector< dataType > &a) { // 1
    return a[0];
}

template< typename dataType >
dataType extractHeapMaximum(vector< dataType > &a) { // log(n)
    int n = int(a.size());
    if(n == 0) {
        throw underflow_error("Error: Heap is empty");
    }
    int mx = a[0];
    swap(a[0], a[n - 1]);
    a.pop_back();
    n = int(a.size());
    maxHeapify(a, 0, n - 1);
    return mx;
}

template< typename dataType >
void heapIncreaseKey(vector< dataType > &a, int i, int newValue) { // log(n)
    if(newValue < a[i]) {
        throw invalid_argument("Error: the new key is smaller than the current one");
    }
    a[i] = newValue;
    while(i > 0 && a[parent(i)] < a[i]) {
        swap(a[parent(i)], a[i]);
        i = parent(i);
    }
}

template< typename dataType >
void insert(vector< dataType > &a, int newValue) { // log(n)
    // a.push_back(-inf) when integer
    a.push_back(newValue); // also valid and general for any dataType
    int n = int(a.size());
    heapIncreaseKey(a, n - 1, newValue);
}

int main() {
    return 0;
}