網站首頁 編程語言 正文
有關二叉樹的性質：
1. 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有 個結點.
2. 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是 .
3. 對任何一棵二叉樹, 如果度為0其葉結點個數為 , 度為2的分支結點個數為 ,則有 ＝ ＋1
4. 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h= . (ps： 是log以2 為底，n+1為對數)
5. 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有節點從0開始編號，則對 于序號為i的結點有：
1. 若i>0，i位置節點的雙親序號：(i-1)/2；i=0，i為根節點編號，無雙親節點
2. 若2i+1<n,左孩子序號：2i+1 若2i+1>=n則無左孩子
3. 若2i+2<n,右孩子序號：2i+2 若2i+2>=n則無右孩子
有關堆
存儲結構：
二叉樹一般可以使用兩種結構存儲，一種順序結構，一種鏈式結構。
普通的二叉樹是不適合用數組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結 構存儲。現實中我們通常把堆(一種完全二叉樹)使用順序結構的數組來存儲
堆的概念和結構：
堆的性質：
堆中某個節點的值總是不大于或不小于其父節點的值；
堆總是一棵完全二叉樹。
上面這些都是復制粘貼的， 想看了隨便看看。下面給出自己的一些總結：
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;
// }
//}
}
void Heap::AdjustDown(int size,int parent) // size 是總大小，parent是從哪里開始向下調整
{
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這個類 物理結構就是一個一維數組，只是邏輯結構是一個堆，我們將其想象成一個具有特定規律的完全二叉樹：特定規律就是任意一個二叉樹的根節點都>=或<=其子節點。
這個Heap類的關鍵是push和pop函數，與之相關的是向上調整和向下調整函數，這也是堆的精髓所在。
push是在數組尾部也就是堆的最下面插入一個元素，此時應該調用向上調整算法，因為此結點的插入可能破壞了原來的堆的結構，因此，向上調整即可，但是有個前提，即插入此結點之前這個完全二叉樹本身符合堆的特性。并且調整只會影響此插入結點的祖宗，不會對其他節點產生影響。
pop是刪除堆頂的元素，且只能刪除堆頂的元素，因為堆這個數據結構的一個主要功能就是選數：即選出當前堆中最大或者最小的數，并且選數的效率很高。pop刪除堆頂元素之后，再進行一下調整即可選出次大或者次小的元素。
那么，怎么刪除呢？即將堆頂和末尾的數字交換，然后刪除交換后的末尾數字，此時堆頂元素很可能破壞了堆的結構，因此采用向下調整的算法。向下調整算法有一個前提：左右子樹必須是一個堆，才能調整。
堆的應用
向上調整算法和向下調整算法不僅僅用于Heap的插入和刪除操作，在堆排序等堆的應用中也要使用。
堆排序
傳入一個數組，對數組進行排序，且是一個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是從哪里開始向下調整
{
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)
{
// 將傳入的數組看作一個完全二叉樹，然后調整為堆。
// 升序調整為大根堆，降序小根堆。
// 建堆方式1： O(N*LogN)
// 利用向上調整算法,其實就是堆的插入函數
//for (int i = 1; i < n; ++i)
//{
// AdjustUp(a, i);
//}
// 建堆方式2： O(N)
// 利用向下調整算法
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--;
}
}前面說過，堆的一個主要或者說唯一作用就是選數，大根堆選出最大數，小根堆選出最小數，先將給定數組調整為堆，若排升序則調整為大根堆，此時a[0]即最大值，將其與數組末尾數組交換，然后進行向下調整即可選出次大值，再進行交換即可。整個邏輯十分像Heap類的刪除操作，只是將刪除了的堆頂元素放置在數組末尾而已，然后不斷進行這個操作，直到整個數組有序。
將數組調整為堆的思路有兩個，一種是模擬插入的操作，從頭遍歷逐個將元素進行向上調整操作，主要是因為向上調整算法必須基于此完全二叉樹本身就是一個堆，才可以進行向上調整操作。所以從尾開始向上調整肯定是不行的。
思路二與思路一有相同之處，即利用向下調整算法，向下調整基于此結點的左子樹和右子樹都是堆，所以直接從頭開始向下調整不可以，所以從尾向前遍歷進行向下調整，且末尾的葉子結點沒有必要調整，所以從第一個結點數>=2的二叉樹開始進行向下調整。
HeapSort的邏輯不會受升序和降序的影響，只需要將AdjustUp和AdjustDown的調整邏輯改變即可。
為什么排升序要建大根堆，不建小根堆呢？
首先，如果建小根堆，確實建好之后的數組比較像升序，且此時最小值也已經在數組的a[0]處，但是，選次大的元素時，對于后面a[1] 至 a[n-1]個元素，此時之前堆的兄弟父子關系全都亂了，向上調整和向下調整都不可以，只能重建堆，而重建堆的時間復雜度為O(N)。如此下去，每次挑出最大值都需要O(N)，最終的就是O(N)+O(N-1)+...+O(2)... 總的就是O(N^2)了。
而如果建大根堆，a[0]就是最大值，將其與數組末尾進行交換，這個交換操作只是O(1)的操作，最重要的是交換之后，把末尾元素忽視之后的這個完全二叉樹，只有堆頂元素不符合堆，只需向下調整一次即可，為O(logN),即可選出次大值，相比于前面的O(N)就快了很多。
原文鏈接：https://blog.csdn.net/i777777777777777/article/details/125027987
相關推薦
- 2022-07-22 Python函數默認參數避坑指南
- 2022-07-19 Python數據分析之NumPy常用函數使用詳解_python
- 2022-02-01 for循環中嵌套異步請求導致順序錯亂
- 2023-09-18 Tomcat控制臺中文亂碼
- 2022-03-15 3 Segmentation fault (core dumped) ./a.out Exited
- 2022-07-25 通過底層源碼理解YOLOv5的Backbone_python
- 2022-12-06 Android?SwipeRefreshLayout超詳細講解_Android
- 2022-11-19 Compose?動畫藝術之屬性動畫探索_Android
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速