AlgortihmsAssignmentOne/Heap.cpp at master · AhmedElsayed2004/AlgortihmsAssignmentOne · 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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include "Heap.h"
template<typename T>
void Heap<T>::insert(T element) {
    if(!isMaxHeap){
        buildMaxHeap(size);
        isMaxHeap=1;
    }
    size++;
    heap.push_back(element);
    int i = size-1;
    while (i != 0 && heap[(i-1)/2] < heap[i]) {
        swap(heap[i], heap[(i-1)/2]);
        i = (i-1)/2;
    }

}
template<typename T>
void Heap<T>::insert(T arr[],int size){
    for(int element = 0; element <size; element++){
        this->insert(arr[element]);
    }

}
template<typename T>
T Heap<T>::extractMax() {
    if(!isMaxHeap){
        buildMaxHeap(size);
        isMaxHeap=1;
    }
    if(size==0){
        throw std::runtime_error("\nheap is empty!\n");
    }else{
        int last = size-1;
        size--;
        swap(heap[0],heap[last]);
        T max = heap[last] ;
        heap.pop_back();
        maxHeapify(0);
        return max ;

    }
}
template<typename T>
void Heap<T>::buildMaxHeap(int size){
    for (int i = 0; i < size; ++i) {
        maxHeapify(i);
    }
}
template<typename T>
void Heap<T>::buildMinHeap(int size){
    for(int perant = (size/2)-1; perant >=0 ; perant--){
        minHeapify(perant);
    }

}
template<typename T>
T Heap<T>::extractMin() {
    if(isMaxHeap){
        buildMinHeap(size);
        isMaxHeap=0;
    }
    if(size==0){
        throw std::runtime_error("\nheap is empty!\n");
    }else{
        int last = size-1;
        size--;
        swap(heap[0],heap[last]);
        int min =heap[last] ;
        heap.pop_back();
        minHeapify(0);
        return min ;

    }
}
template<typename T>
void Heap<T>::maxHeapify(int perant) {
    int leftChild = 2*perant+1,rightChild = 2*perant+2,current;
    while(leftChild<size){
        if(heap[leftChild]<heap[rightChild] and rightChild < size){
            current=rightChild;
        }else{
            current= leftChild;
        }
        if(heap[perant]<heap[current]){
            swap(heap[perant],heap[current]);
            perant=current;
            leftChild=2*perant+1;
            rightChild=2*perant+2;
        }else{
            break;
        }
    }
}
template<typename T>
void Heap<T>::minHeapify(int perant) {

    int leftChild = 2*perant+1,rightChild = 2*perant+2,current;
    while(leftChild<size){
        if(heap[leftChild]>heap[rightChild] and rightChild < size){
            current=rightChild;
        }else{
            current= leftChild;
        }
        if(heap[perant]>heap[current]){
            swap(heap[perant],heap[current]);
            perant=current;
            leftChild=2*perant+1;
            rightChild=2*perant+2;
        }else{
            break;
        }
    }

}