【C++】基于数组实现的最小堆
{:10_297:} 初学数据结构，欢迎指正。#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;
maxSize = size;
heapSize = 0;
}
template <typename T>
MinHeap<T>::MinHeap(T arr[], int size) {
maxSize = (size > MAX_SIZE) ? size : MAX_SIZE;
heap = new T;
heapSize = size;
for (int i = 0; i < size; i++) {
heap = arr;
}
_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;
for (int i = 0; i < maxSize; i++) {
hn = heap;
}
delete[] heap;
heap = hn;
}
heap = value;
_SiftUp(heapSize);
heapSize++;
}
template <typename T>
void MinHeap<T>::forShow() {
for (int i = 0; i < heapSize; i++) {
cout << heap << 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 < heap) {
temp = heap;
heap = heap;
heap = temp;
}
j = (k + 1) * 2 - 1;
while (j <= heapSize - 1 && heap > heap) {
temp = heap;
heap = heap;
heap = 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;
//while中不作交换，只把较大的父节点往下填
while (i > 0) {
if (temp < heap) {
heap = heap;
i = j;
j = (i - 1) / 2;
}
else {
break;
}
}
//填入正确位置
heap = 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;
return true;
}
}
template <typename T>
bool MinHeap<T>::remove(T &value) {
if (heapSize == 0) {
return false;
}
else {
value = heap;
remove();
return true;
}
}
template <typename T>
void MinHeap<T>::remove() {
if (heapSize == 0) {
return;
}
heapSize--;
heap = heap;
_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()原理图{:10_256:}
页:
[1]