【C++】基于数组实现的最小堆

膜法记者

初学数据结构，欢迎指正。

#include<iostream>
using namespace std;

template <typename T>
class MinHeap {
private:
        const static int MAX_SIZE = 20;
        const static int EX_SIZE = 20;
        int heapSize;
        int maxSize;
        T *heap;
        void _sort(); // 整体排序
        void _sortUp(int start); // 上滑排序
public:
        MinHeap(int size = MAX_SIZE);
        MinHeap(T arr[], int size);
        ~MinHeap();
        void insert(const T& value); // 插入新结点
        void forShow(); // 遍历数组输出，仅用于测试
        int getSize();
        int getMaxSize();
        bool getTop(T &value);
        bool remove(T &value);
        void remove();
        void makeEmpty();
};

template <typename T>
MinHeap<T>::MinHeap(int size) {
        heap = new T[size];
        maxSize = size;
        heapSize = 0;
}

template <typename T>
MinHeap<T>::MinHeap(T arr[], int size) {
        maxSize = (size > MAX_SIZE) ? size : MAX_SIZE;
        heap = new T[maxSize];
        heapSize = size;
        for (int i = 0; i < size; i++) {
                heap[i] = arr[i];
        }
        _sort();
}

template <typename T>
MinHeap<T>::~MinHeap() {
        delete[] heap;
}

template <typename T>
void MinHeap<T>::insert(const T& value) {
        if (heapSize == maxSize) {
                T *hn = new T[maxSize + EX_SIZE];
                for (int i = 0; i < maxSize; i++) {
                        hn[i] = heap[i];
                }
                delete[] heap;
                heap = hn;
        }
        heap[heapSize] = value;
        _SiftUp(heapSize);
        heapSize++;
}

template <typename T>
void MinHeap<T>::forShow() {
        for (int i = 0; i < heapSize; i++) {
                cout << heap[i] << endl;
        }
}

template <typename T>
void MinHeap<T>::_sort() {
        int i, j, k;
        T temp;
        for (i = heapSize - 1; i > 0; i--) {
                k = i;
                j = (k - 1) / 2;
                if (heap[k] < heap[j]) {
                        temp = heap[k];
                        heap[k] = heap[j];
                        heap[j] = temp;
                }
                j = (k + 1) * 2 - 1;
                while (j <= heapSize - 1 && heap[k] > heap[j]) {
                        temp = heap[k];
                        heap[k] = heap[j];
                        heap[j] = temp;
                        k = j;
                        j = (j + 1) * 2 - 1;
                }
        }
}

template <typename T>
void MinHeap<T>::_sortUp(int start) {
        int i = start;
        int j = (i - 1) / 2;
        T temp = heap[i];
        //while中不作交换，只把较大的父节点往下填
        while (i > 0) {
                if (temp < heap[j]) {
                        heap[i] = heap[j];
                        i = j;
                        j = (i - 1) / 2;
                }
                else {
                        break;
                }
        }
        //填入正确位置
        heap[i] = temp;
}

template <typename T>
int MinHeap<T>::getSize() {
        return heapSize;
}

template <typename T>
int MinHeap<T>::getMaxSize() {
        return maxSize;
}

template <typename T>
bool MinHeap<T>::getTop(T &value) {
        if (heapSize == 0) {
                return false;
        }
        else {
                value = heap[0];
                return true;
        }
}

template <typename T>
bool MinHeap<T>::remove(T &value) {
        if (heapSize == 0) {
                return false;
        }
        else {
                value = heap[0];
                remove();
                return true;
        }
}

template <typename T>
void MinHeap<T>::remove() {
        if (heapSize == 0) {
                return;
        }
        heapSize--;
        heap[0] = heap[heapSize];
        _sort();
}

template <typename T>
void MinHeap<T>::makeEmpty() {
        heapSize = 0;
}

以下是测试代码

int main() {
        int a[] = {53,17,78,9,45,65,87,23};
        MinHeap<int> h(a,8);
        h.forShow();
        return 0;
}

如果T是一个类，要求它必须重载了>、<、>=等运算符
附_sort()和_sortUp()原理图