project_cpp_24/maxHeap.cpp at master · Bobi222/project_cpp_24 · 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
#include "MaxHeap.h"
#include <stdexcept>
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

MaxHeap::MaxHeap() {
    heap = NULL;
    currentSize = 0;
}

MaxHeap::~MaxHeap() {
    delete[] heap;
}

bool MaxHeap::insert(int element) {
    // Check for duplicates
    for (int i = 0; i < currentSize; i++) {
        if (heap[i] == element) {
            return false;
        }
    }

    resizeHeap(currentSize + 1);
    heap[currentSize] = element;
    heapifyUp(currentSize);
    currentSize++;

    return true;
}

int MaxHeap::extractMax() {
    if (currentSize <= 0) {
        throw runtime_error("Heap is empty");
    }
    int max = heap[0];
    currentSize--;
    heap[0] = heap[currentSize];
    heapifyDown(0);
    resizeHeap(currentSize);
    return max;
}

int MaxHeap::getMax() const {
    if (currentSize <= 0) {
        throw runtime_error("Heap is empty");
    }
    return heap[0];
}

int MaxHeap::getSize() const {
    return currentSize;
}

void MaxHeap::heapifyUp(int index) {
    while (index != 0 && heap[parent(index)] < heap[index]) {
        swap(heap[parent(index)], heap[index]);
        index = parent(index);
    }
}

void MaxHeap::heapifyDown(int index) {
    int largest = index;
    int left = leftChild(index);
    int right = rightChild(index);

    if (left < currentSize && heap[left] > heap[largest]) {
        largest = left;
    }
    if (right < currentSize && heap[right] > heap[largest]) {
        largest = right;
    }

    if (largest != index) {
        swap(heap[index], heap[largest]);
        heapifyDown(largest);
    }
}

int MaxHeap::parent(int index) const {
    return (index - 1) / 2;
}

int MaxHeap::leftChild(int index) const {
    return 2 * index + 1;
}

int MaxHeap::rightChild(int index) const {
    return 2 * index + 2;
}

void MaxHeap::resizeHeap(int newSize) {
    int* newHeap = new int[newSize];
    if (heap) {
        memcpy(newHeap, heap, sizeof(int) * min(newSize, currentSize));
        delete[] heap;
    }
    heap = newHeap;
}