C++超详细实现堆和堆排序过像-C/C++开发

堆是计算机科学中一类特殊的数据结构的统称，通常是一个可以被看做一棵完全二叉树的数组对象。而堆排序是利用堆这种数据结构所设计的一种排序算法。本文将通过图片详细介绍堆排序，需要的可以参考一下

有关堆

存储结构：

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种完全二叉树)使用顺序结构的数组来存储

堆的概念和结构：

IiBzcmM9

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

上面这些都是复制粘贴的，想看了随便看看。下面给出自己的一些总结：

C++实现堆

Heap.h

#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
#include<Windows.h>
using namespace std;
typedef int DataType;
class Heap
{
public:
	Heap() :a(new DataType[1]), size(0), capacity(1) {}
	~Heap()
	{
		delete[]a;
		a = nullptr;
		size = capacity = 0;
	}
public:
	void Push(const DataType& x);
	void Pop();    // 删除堆顶的数据
	DataType Top()const;
	bool Empty()const;
	int Size()const;
	void Swap(DataType& a, DataType& b);
	void print();
public:
	void AdjustUp(int child);
	void AdjustDown(int size, int parent);
private:
	DataType* a;
	int size;
	int capacity;
};

Heap.cpp

#include"Heap.h"
void Heap::Swap(DataType& a, DataType& b)
{
	DataType tmp = a;
	a = b;
	b = tmp;
}
void Heap::Push(const DataType& x)
{
	if (size == capacity)
	{
		int newcapacity = capacity == 0 ? 1 : capacity * 2;
		DataType* tmp = new DataType[newcapacity];
		assert(tmp);
		std::copy(a, a + size, tmp);
		delete a;
		a = tmp;
		capacity = newcapacity;
	}
	a[size] = x;
	AdjustUp(size);
	++size;
}
void Heap::Pop() // 删除堆顶的数据
{
	assert(size > 0);
	Swap(a[0], a[size - 1]);
	size--;
	AdjustDown(size, 0);
}
DataType Heap::Top()const
{
	assert(size > 0);
	return a[0];
}
bool Heap::Empty()const
{
	return size == 0;
}
int Heap::Size()const
{
	return size;
}
void Heap::AdjustUp(int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			Swap(a[parent], a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
	//int parent = (child - 1) / 2;
	//if(child > 0)
	//{
	//	if (a[parent] > a[child])
	//	{
	//		Swap(a[parent], a[child]);
	//		child = parent;
	//		AdjustUp(child);
	//	}
	//	else
	//	{
	//		return;
	//	}
	/

目录

有关堆

C++实现堆