heap.h
#pragma once
#include<iostream>
using namespace std;
typedef int datatype;
class heap
{
public:
heap(int a=4); //构造，缺省值默认给4个空间的大小
void push(datatype a); //入数据
void kuorong(); //扩容
void swap(datatype& a, datatype& b); //交换
void adjustup(); //向上调整
datatype deletetop(); //删除对顶数据并返回堆顶数据
void adjustdown(); //向下调整
datatype* heapsort(); //排个序
~heap(); //析构
void look(); //看一看堆的结构(用于测试观察，只能看4排)
datatype* lty; //堆的底层是个数组
int size; //堆中的数据个数
int capacity; //堆的容量
};
heap.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
void heap::look() //看一看堆的结构
{
cout << " " << lty[0] << endl;
int k = 1;
if (k > 0 && k <= 2&&k<size)
{
for (; k < size && k <= 2; k++)
{
cout << " " << lty[k];
}
cout << endl;
}
if (k > 2 && k <= 6)
{
for (; k < size && k <= 6; k++)
{
cout << " " << lty[k];
}cout << endl;
}
if (k > 6 && k <= 15)
{
for (; k < size && k <= 15; k++)
{
cout << " " << lty[k];
}cout << endl;
}
cout << endl << endl;
}
void heap::swap(datatype& a, datatype& b) //交换
{
datatype t = a;
a = b;
b = t;
}
heap::heap(int a) //构造（缺省值只写在声明）
:size(0), //初始化列表会把类中的变量按声明的顺序初始化
capacity(a) //如果先开空间，size为随机值，所以不能把数组写在列表里。
{
lty = new datatype[a]{0,0,0,0}; //随意初始化一下
}
heap::~heap() //析构
{
delete[]lty;
lty = nullptr;
size = capacity = 0;
}
void heap::push(datatype a) //如数据
{
if (size==capacity) //空间不够需要扩容
{
(*this).kuorong(); //可以不用写*this
}
lty[size] = a;
size++;
look(); //查看一下是否入成功
heap::adjustup(); //在数组末尾添加了数据需要向上调整
}
void heap::kuorong() //扩容
{
int k = capacity * 1.5; //每次扩容1.5倍
datatype* t = (datatype*)realloc(lty, k * sizeof(datatype));
lty = t;
capacity = k;
}
void heap::adjustup() //向上调整
{
int pos = size - 1; //pos是最后一个元素的下标
while (pos > 0)
{
if (lty[pos] < lty[(pos - 1) / 2]) //当最后一个元素比它的parent小的时候
{
heap::swap(lty[pos], lty[(pos - 1) / 2]); //交换
}
else
{
break;
}
pos = (pos - 1) / 2; //每次交换完让pos等于上一次的pos的parent
} //然后继续用新的pos与pos的parent比较/交换
}
datatype heap::deletetop() //删除堆顶元素并返回堆顶元素
{
datatype re = lty[0]; //记录下堆顶元素的值
lty[0] = lty[size-1]; //把最后一个元素移到堆顶来
size--; //相当于删除了一个元素
adjustdown(); //把堆顶元素(之前的最后一个)向下调整
return re; //返回之前删除的堆顶元素
}
void heap::adjustdown() //向下调整
{
int parentpos = 0; //记录下parent的下标
int smallchild = parentpos * 2 + 1; //假设parent的较小孙节点的下标为左孙节点
while (parentpos*2+1<size) //parent子节点的下标在size范围内的时候
{
if (lty[smallchild] > lty[smallchild + 1]) //如果左孙大于右孙
{
smallchild++; //就让假设的左孙下标变成右孙下标
}
if (lty[smallchild] < lty[parentpos]) //如果孙比parent小
{
swap(lty[smallchild], lty[parentpos]); //就让孙和parent交换
parentpos = smallchild; //让parent等于刚才的孙
smallchild = parentpos * 2 + 1; //假设小孙是parent的左孙
}
else
{
break; //如果孙==parent或者孙>parent就跳出while循环
}
}
}
datatype* heap::heapsort() //排个序并返回排序后的数组
{
datatype * arr = new datatype[size*sizeof(datatype)]; //new一个新的数组
int sizea = size; //提前把size记录下来，因为出堆顶数据的时候会size--
for (int k = 0; k < sizea; k++) //出堆顶数据的同时把返回的堆顶的值存到arr数组里
{
arr[k] = deletetop();
}
for (int m = 0; m < sizea; m++) //查看一下排序之后的数组
{
cout << arr[m] << " ";
}
cout << endl << endl;
return arr; //把排序好的数组返回去
}
test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
void test()
{
heap a(8); //构造一个队
a.push(3); //一直入数据
a.push(5);
a.push(11);
a.push(4);
a.push(12);
a.push(21);
a.push(15);
a.push(7);
a.look(); //查看一下堆
cout << endl << endl;
cout << a.deletetop() << endl; //删除堆顶数据看一下
a.look(); //再看看堆
cout << a.deletetop() << endl; //在删除一个
a.look(); //再看一下
a.heapsort(); //排个序看一下
}
int main()
{
test(); //测试函数
return 0;
}
