C++超詳細(xì)實(shí)現(xiàn)堆和堆排序過(guò)像
有關(guān)二叉樹(shù)的性質(zhì)：
1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹(shù)的第i層上最多有 個(gè)結(jié)點(diǎn).
2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是 .
3. 對(duì)任何一棵二叉樹(shù), 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為 , 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為 ,則有 ＝ ＋1
4. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)的深度，h= . (ps： 是log以2 為底，n+1為對(duì)數(shù))
5. 對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開(kāi)始編號(hào)，則對(duì) 于序號(hào)為i的結(jié)點(diǎn)有：
1. 若i>0，i位置節(jié)點(diǎn)的雙親序號(hào)：(i-1)/2；i=0，i為根節(jié)點(diǎn)編號(hào)，無(wú)雙親節(jié)點(diǎn)
2. 若2i+1<n,左孩子序號(hào)：2i+1 若2i+1>=n則無(wú)左孩子
3. 若2i+2<n,右孩子序號(hào)：2i+2 若2i+2>=n則無(wú)右孩子
有關(guān)堆
存儲(chǔ)結(jié)構(gòu)：
二叉樹(shù)一般可以使用兩種結(jié)構(gòu)存儲(chǔ)，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。
普通的二叉樹(shù)是不適合用數(shù)組來(lái)存儲(chǔ)的，因?yàn)榭赡軙?huì)存在大量的空間浪費(fèi)。而完全二叉樹(shù)更適合使用順序結(jié) 構(gòu)存儲(chǔ)?，F(xiàn)實(shí)中我們通常把堆(一種完全二叉樹(shù))使用順序結(jié)構(gòu)的數(shù)組來(lái)存儲(chǔ)
堆的概念和結(jié)構(gòu)：
堆的性質(zhì)：
堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
堆總是一棵完全二叉樹(shù)。
上面這些都是復(fù)制粘貼的， 想看了隨便看看。下面給出自己的一些總結(jié)：
C++實(shí)現(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是從哪里開(kāi)始向下調(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;
}其實(shí)Heap這個(gè)類(lèi) 物理結(jié)構(gòu)就是一個(gè)一維數(shù)組，只是邏輯結(jié)構(gòu)是一個(gè)堆，我們將其想象成一個(gè)具有特定規(guī)律的完全二叉樹(shù)：特定規(guī)律就是任意一個(gè)二叉樹(shù)的根節(jié)點(diǎn)都>=或<=其子節(jié)點(diǎn)。
這個(gè)Heap類(lèi)的關(guān)鍵是push和pop函數(shù)，與之相關(guān)的是向上調(diào)整和向下調(diào)整函數(shù)，這也是堆的精髓所在。
push是在數(shù)組尾部也就是堆的最下面插入一個(gè)元素，此時(shí)應(yīng)該調(diào)用向上調(diào)整算法，因?yàn)榇私Y(jié)點(diǎn)的插入可能破壞了原來(lái)的堆的結(jié)構(gòu)，因此，向上調(diào)整即可，但是有個(gè)前提，即插入此結(jié)點(diǎn)之前這個(gè)完全二叉樹(shù)本身符合堆的特性。并且調(diào)整只會(huì)影響此插入結(jié)點(diǎn)的祖宗，不會(huì)對(duì)其他節(jié)點(diǎn)產(chǎn)生影響。
pop是刪除堆頂?shù)脑?，且只能刪除堆頂?shù)脑?，因?yàn)槎堰@個(gè)數(shù)據(jù)結(jié)構(gòu)的一個(gè)主要功能就是選數(shù)：即選出當(dāng)前堆中最大或者最小的數(shù)，并且選數(shù)的效率很高。pop刪除堆頂元素之后，再進(jìn)行一下調(diào)整即可選出次大或者次小的元素。
那么，怎么刪除呢？即將堆頂和末尾的數(shù)字交換，然后刪除交換后的末尾數(shù)字，此時(shí)堆頂元素很可能破壞了堆的結(jié)構(gòu)，因此采用向下調(diào)整的算法。向下調(diào)整算法有一個(gè)前提：左右子樹(shù)必須是一個(gè)堆，才能調(diào)整。
堆的應(yīng)用
向上調(diào)整算法和向下調(diào)整算法不僅僅用于Heap的插入和刪除操作，在堆排序等堆的應(yīng)用中也要使用。
堆排序
傳入一個(gè)數(shù)組，對(duì)數(shù)組進(jìn)行排序，且是一個(gè)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是從哪里開(kāi)始向下調(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ù)組看作一個(gè)完全二叉樹(shù)，然后調(diào)整為堆。
// 升序調(diào)整為大根堆，降序小根堆。
// 建堆方式1： O(N*LogN)
// 利用向上調(diào)整算法,其實(shí)就是堆的插入函數(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);
}
// 建好堆之后排序 目前是一個(gè)小堆，小堆用來(lá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--;
}
}前面說(shuō)過(guò)，堆的一個(gè)主要或者說(shuō)唯一作用就是選數(shù)，大根堆選出最大數(shù)，小根堆選出最小數(shù)，先將給定數(shù)組調(diào)整為堆，若排升序則調(diào)整為大根堆，此時(shí)a[0]即最大值，將其與數(shù)組末尾數(shù)組交換，然后進(jìn)行向下調(diào)整即可選出次大值，再進(jìn)行交換即可。整個(gè)邏輯十分像Heap類(lèi)的刪除操作，只是將刪除了的堆頂元素放置在數(shù)組末尾而已，然后不斷進(jìn)行這個(gè)操作，直到整個(gè)數(shù)組有序。
將數(shù)組調(diào)整為堆的思路有兩個(gè)，一種是模擬插入的操作，從頭遍歷逐個(gè)將元素進(jìn)行向上調(diào)整操作，主要是因?yàn)橄蛏险{(diào)整算法必須基于此完全二叉樹(shù)本身就是一個(gè)堆，才可以進(jìn)行向上調(diào)整操作。所以從尾開(kāi)始向上調(diào)整肯定是不行的。
思路二與思路一有相同之處，即利用向下調(diào)整算法，向下調(diào)整基于此結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都是堆，所以直接從頭開(kāi)始向下調(diào)整不可以，所以從尾向前遍歷進(jìn)行向下調(diào)整，且末尾的葉子結(jié)點(diǎn)沒(méi)有必要調(diào)整，所以從第一個(gè)結(jié)點(diǎn)數(shù)>=2的二叉樹(shù)開(kāi)始進(jìn)行向下調(diào)整。
HeapSort的邏輯不會(huì)受升序和降序的影響，只需要將AdjustUp和AdjustDown的調(diào)整邏輯改變即可。
為什么排升序要建大根堆，不建小根堆呢？
首先，如果建小根堆，確實(shí)建好之后的數(shù)組比較像升序，且此時(shí)最小值也已經(jīng)在數(shù)組的a[0]處，但是，選次大的元素時(shí)，對(duì)于后面a[1] 至 a[n-1]個(gè)元素，此時(shí)之前堆的兄弟父子關(guān)系全都亂了，向上調(diào)整和向下調(diào)整都不可以，只能重建堆，而重建堆的時(shí)間復(fù)雜度為O(N)。如此下去，每次挑出最大值都需要O(N)，最終的就是O(N)+O(N-1)+...+O(2)... 總的就是O(N^2)了。
而如果建大根堆，a[0]就是最大值，將其與數(shù)組末尾進(jìn)行交換，這個(gè)交換操作只是O(1)的操作，最重要的是交換之后，把末尾元素忽視之后的這個(gè)完全二叉樹(shù)，只有堆頂元素不符合堆，只需向下調(diào)整一次即可，為O(logN),即可選出次大值，相比于前面的O(N)就快了很多。
到此這篇關(guān)于C++超詳細(xì)實(shí)現(xiàn)堆和堆排序過(guò)像的文章就介紹到這了,更多相關(guān)C++堆和堆排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C語(yǔ)言中#pragma?once的作用，pragma once 一般由編譯器提供保證，更多相關(guān)內(nèi)容在下面文章詳細(xì)展開(kāi)需要的小伙伴可以參考一下2022-05-05
這篇文章主要介紹了C語(yǔ)言規(guī)律循環(huán)累加求和案例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-12-12
C++實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過(guò)程詳解
動(dòng)態(tài)規(guī)劃是解決一類(lèi)最優(yōu)問(wèn)題的常用方法，它是解決最優(yōu)化問(wèn)題的一種途徑，在本文中，我們將討論如何使用C++實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法，并提供一些示例來(lái)幫助您更好地理解該算法2023-05-05
C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)順序表詳解
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)順序表的實(shí)現(xiàn)代碼的相關(guān)資料,動(dòng)態(tài)順序表在內(nèi)存中開(kāi)辟一塊空間，可以隨我們數(shù)據(jù)數(shù)量的增多來(lái)擴(kuò)容，需要的朋友可以參考下2021-08-08
C++中?‘=default?’及‘?=delete?’的使用
這篇文章主要介紹了C++中?=default?及?=delete?使用，使用=default和=delete可以控制編譯器默認(rèn)函數(shù)體的使用，下面我們就來(lái)看看具體的室友方法吧,需要的朋友也可以參考一下2021-12-12
C++線(xiàn)程池的簡(jiǎn)單實(shí)現(xiàn)方法
這篇文章主要介紹了C++線(xiàn)程池的簡(jiǎn)單實(shí)現(xiàn)方法,包括了線(xiàn)程操作函數(shù)及相關(guān)屬性的用法,需要的朋友可以參考下2014-09-09
C語(yǔ)言動(dòng)態(tài)內(nèi)存的分配實(shí)例詳解
動(dòng)態(tài)內(nèi)存管理同時(shí)還具有一個(gè)優(yōu)點(diǎn),當(dāng)程序在具有更多內(nèi)存的系統(tǒng)上需要處理更多數(shù)據(jù)時(shí),不需要重寫(xiě)程序,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言動(dòng)態(tài)內(nèi)存分配的相關(guān)資料,需要的朋友可以參考下2022-06-06
vscode是一款越來(lái)越受碼農(nóng)們喜愛(ài)的軟件，大多數(shù)人學(xué)習(xí)編程繞不開(kāi)的一部分就是算法，很多人都喜歡刷LeetCode的題目，本文就來(lái)介紹一下2021-06-06
深入理解C語(yǔ)言sizeof()計(jì)算空間大小為8的問(wèn)題
本文將介紹C語(yǔ)言中的sizeof()函數(shù),以及如何使用它來(lái)計(jì)算變量、數(shù)據(jù)類(lèi)型和數(shù)組在內(nèi)存中的大小,具有一定的參考價(jià)值,感興趣的可以了解一下2023-09-09
C語(yǔ)言實(shí)現(xiàn)教務(wù)管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)教務(wù)管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03