快捷導(dǎo)航

C++超詳細實現(xiàn)堆和堆排序過像

更新時間：2022年06月24日 10:50:40 作者：配的上了嗎

堆是計算機科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱，通常是一個可以被看做一棵完全二叉樹的數(shù)組對象。而堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。本文將通過圖片詳細介紹堆排序，需要的可以參考一下

有關(guān)堆

存儲結(jié)構(gòu)：

二叉樹一般可以使用兩種結(jié)構(gòu)存儲，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。

普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結(jié) 構(gòu)存儲?，F(xiàn)實中我們通常把堆(一種完全二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲

堆的概念和結(jié)構(gòu)：

堆的性質(zhì)：

堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；

堆總是一棵完全二叉樹。

上面這些都是復(fù)制粘貼的，想看了隨便看看。下面給出自己的一些總結(jié)：

C++實現(xiàn)堆

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();    // 刪除堆頂?shù)臄?shù)據(jù)
	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() // 刪除堆頂?shù)臄?shù)據(jù)
{
	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;
	//	}
	//}
}
void Heap::AdjustDown(int size,int parent) // size 是總大小，parent是從哪里開始向下調(diào)整 
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] < a[child])
			child++;
		if (a[child] < a[parent])
		{
			Swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void Heap::print()
{
	for (int i = 0; i < size; ++i)
	{
		cout << a[i] << ' ';
	}
	cout << endl;
}

其實Heap這個類物理結(jié)構(gòu)就是一個一維數(shù)組，只是邏輯結(jié)構(gòu)是一個堆，我們將其想象成一個具有特定規(guī)律的完全二叉樹：特定規(guī)律就是任意一個二叉樹的根節(jié)點都>=或<=其子節(jié)點。

這個Heap類的關(guān)鍵是push和pop函數(shù)，與之相關(guān)的是向上調(diào)整和向下調(diào)整函數(shù)，這也是堆的精髓所在。

push是在數(shù)組尾部也就是堆的最下面插入一個元素，此時應(yīng)該調(diào)用向上調(diào)整算法，因為此結(jié)點的插入可能破壞了原來的堆的結(jié)構(gòu)，因此，向上調(diào)整即可，但是有個前提，即插入此結(jié)點之前這個完全二叉樹本身符合堆的特性。并且調(diào)整只會影響此插入結(jié)點的祖宗，不會對其他節(jié)點產(chǎn)生影響。

pop是刪除堆頂?shù)脑兀抑荒軇h除堆頂?shù)脑?，因為堆這個數(shù)據(jù)結(jié)構(gòu)的一個主要功能就是選數(shù)：即選出當(dāng)前堆中最大或者最小的數(shù)，并且選數(shù)的效率很高。pop刪除堆頂元素之后，再進行一下調(diào)整即可選出次大或者次小的元素。

那么，怎么刪除呢？即將堆頂和末尾的數(shù)字交換，然后刪除交換后的末尾數(shù)字，此時堆頂元素很可能破壞了堆的結(jié)構(gòu)，因此采用向下調(diào)整的算法。向下調(diào)整算法有一個前提：左右子樹必須是一個堆，才能調(diào)整。

堆的應(yīng)用

向上調(diào)整算法和向下調(diào)整算法不僅僅用于Heap的插入和刪除操作，在堆排序等堆的應(yīng)用中也要使用。

堆排序

傳入一個數(shù)組，對數(shù)組進行排序，且是一個O(N*LogN)的算法，效率很高。

void AdjustUp(int* a, 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;
		}
	}
}
void AdjustDown(int* a,int size, int parent) // size 是總大小，parent是從哪里開始向下調(diào)整 
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] < a[child])
			child++;
		if (a[child] < a[parent])
		{
			swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

HeapSort

void HeapSort(int* a, int n)
{
	// 將傳入的數(shù)組看作一個完全二叉樹，然后調(diào)整為堆。
	// 升序調(diào)整為大根堆，降序小根堆。
	// 建堆方式1： O(N*LogN)
	// 利用向上調(diào)整算法,其實就是堆的插入函數(shù)
	//for (int i = 1; i < n; ++i)
	//{
	//	AdjustUp(a, i);
	//}
	// 建堆方式2： O(N)
	// 利用向下調(diào)整算法
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	// 建好堆之后排序 目前是一個小堆，小堆用來排降序
	// 5 13 17 19 22 27 32 35 38 42 45
    // O(N * LogN);
    int end = n - 1;
	while (end > 0)
	{
		swap(a[0], a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

前面說過，堆的一個主要或者說唯一作用就是選數(shù)，大根堆選出最大數(shù)，小根堆選出最小數(shù)，先將給定數(shù)組調(diào)整為堆，若排升序則調(diào)整為大根堆，此時a[0]即最大值，將其與數(shù)組末尾數(shù)組交換，然后進行向下調(diào)整即可選出次大值，再進行交換即可。整個邏輯十分像Heap類的刪除操作，只是將刪除了的堆頂元素放置在數(shù)組末尾而已，然后不斷進行這個操作，直到整個數(shù)組有序。

將數(shù)組調(diào)整為堆的思路有兩個，一種是模擬插入的操作，從頭遍歷逐個將元素進行向上調(diào)整操作，主要是因為向上調(diào)整算法必須基于此完全二叉樹本身就是一個堆，才可以進行向上調(diào)整操作。所以從尾開始向上調(diào)整肯定是不行的。

思路二與思路一有相同之處，即利用向下調(diào)整算法，向下調(diào)整基于此結(jié)點的左子樹和右子樹都是堆，所以直接從頭開始向下調(diào)整不可以，所以從尾向前遍歷進行向下調(diào)整，且末尾的葉子結(jié)點沒有必要調(diào)整，所以從第一個結(jié)點數(shù)>=2的二叉樹開始進行向下調(diào)整。

HeapSort的邏輯不會受升序和降序的影響，只需要將AdjustUp和AdjustDown的調(diào)整邏輯改變即可。

為什么排升序要建大根堆，不建小根堆呢？

首先，如果建小根堆，確實建好之后的數(shù)組比較像升序，且此時最小值也已經(jīng)在數(shù)組的a[0]處，但是，選次大的元素時，對于后面a[1] 至 a[n-1]個元素，此時之前堆的兄弟父子關(guān)系全都亂了，向上調(diào)整和向下調(diào)整都不可以，只能重建堆，而重建堆的時間復(fù)雜度為O(N)。如此下去，每次挑出最大值都需要O(N)，最終的就是O(N)+O(N-1)+...+O(2)... 總的就是O(N^2)了。

而如果建大根堆，a[0]就是最大值，將其與數(shù)組末尾進行交換，這個交換操作只是O(1)的操作，最重要的是交換之后，把末尾元素忽視之后的這個完全二叉樹，只有堆頂元素不符合堆，只需向下調(diào)整一次即可，為O(logN),即可選出次大值，相比于前面的O(N)就快了很多。

到此這篇關(guān)于C++超詳細實現(xiàn)堆和堆排序過像的文章就介紹到這了,更多相關(guān)C++堆和堆排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: