热门标签
当前位置: article > 正文
数据结构——二叉树的顺序存储（堆）（C++实现）_顺序存储的完全二叉树
作者：从前慢现在也慢 | 2024-08-06 00:35:48
赞
踩
顺序存储的完全二叉树
我们接着来看二叉树：
二叉树可以顺序存储的前提
完全二叉树完全符合顺序存储的前提：
完全二叉树：顺序存储二叉树最适合应用于完全二叉树。完全二叉树是一种特殊的二叉树，除最后一层外，每一层都被完全填满，并且所有结点尽可能集中在左边。由于其结构特性，完全二叉树的结点与数组下标之间存在着直接的数学映射关系，**使得每个结点可以按照固定规则（如左孩子为2i，右孩子为2i+1）**在数组中找到其相应的位置。这种映射保证了数组的存储空间得以充分利用，没有浪费。
顺序存储的二叉树我们称为堆：
堆的定义
堆是一种特殊的树形数据结构，通常以数组的形式进行顺序存储。堆具有以下关键性质：
-
完全二叉树结构：
堆是一个完全二叉树或近乎完全二叉树。这意味着除了可能的最后一层外，其他各层都是完全填充的，并且最后一层的所有结点都尽可能靠左排列。这种结构非常适合用数组来表示，因为完全二叉树的结点与数组下标之间存在直接的数学映射关系，使得每个结点可以高效地通过下标访问。 -
堆序性质：
堆分为两种主要类型：最大堆和最小堆。无论哪种类型，堆都遵循特定的堆序性质：
- 大根堆：每个结点的值都大于或等于其子结点的值。即对于任意结点 i，其值
A[i]大于等于其左孩子A[2*i+1]和右孩子A[2*i+2]的值。- 小根堆：每个结点的值都小于或等于其子结点的值。即对于任意结点 i，其值
A[i]小于等于其左孩子A[2*i+1]和右孩子A[2*i+2]的值。
由于堆的完全二叉树特性和堆序性质，它非常适合使用数组进行顺序存储。具体来说：
- 数组下标与结点关系：
假设数组
A存储了一个堆，根结点位于下标0。那么对于任一结点 i，其左孩子、右孩子的下标分别为2*i + 1和2*i + 2，而其父结点的下标为(i - 1) // 2（向下取整）。这种固定的下标关系使得在数组中进行堆的操作（如插入、删除、调整等）变得非常直观和高效。
- 空间利用率：
由于堆是完全或近乎完全二叉树，其存储在数组中时空间利用率较高。即使不是严格的完全二叉树，只要整体结构相对平衡，数组中的空闲位置也相对较少，不会造成过多的存储浪费。
- 操作复杂度：
堆的常见操作（如插入、删除堆顶元素、调整堆等）的时间复杂度通常为 O(log n)，这是因为堆的高度与结点数成对数关系。数组的随机访问特性使得这些操作能够在常数时间内定位到相关结点，然后通过递归或迭代方式进行堆结构调整。
因此，堆作为一类满足特定条件的二叉树，其完全二叉树特性、堆序性质以及高效的操作性能，使其非常适合采用数组进行顺序存储。堆常用于实现优先队列、求解Top-K问题、堆排序算法等场景。
堆的分类
大根堆
大根堆是一种特殊的二叉堆，其中每个节点的值都大于或等于其子节点的值。具体地说，对于大根堆中的任意节点
i，其值 A[i] 大于等于其左孩子A[2*i+1]和右孩子A[2*i+2]的值。根节点（数组下标为1或0，取决于实现）总是包含堆中的最大值。大根堆常用于实现优先队列，其中队首元素始终为当前最大的元素。
小根堆
小根堆也是一种特殊的二叉堆，其中每个节点的值都小于或等于其子节点的值。对于小根堆中的任意节点 i，其值
A[i]小于等于其左孩子A[2*i+1]和右孩子A[2*i+2]的值。根节点（同样为数组下标为1或0）始终包含堆中的最小值。小根堆同样适用于优先队列的场景，但此时队首元素为当前最小的元素。
整体结构把握
我们这里用vector作为底层容器来存储数据，这些数据按照顺序排放：
#pragma once #include<iostream> #include<vector> template<class T> //堆的定义 class Heap { public: Heap() :_size(0) { _data.resize(10); } Heap(const size_t& size) :_size(0) { _data.resize(size + 1); } //插入 void insert(const T& data) { if(_size > _data.capacity()) { _data.resize(2 * _data.size()); } _data[++_size] = data; } //是否为空 bool empty() { return _size == 0; } //打印堆 void printHeap() { for(int i = 1; i < _size + 1; i++) { std::cout<< _data[i] << " "; } std::cout << std::endl; } private: std::vector<T> _data; //存放数据 size_t _size; //当前数据个数 };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
这里注意一下，我的一个数据并没有放在0号位置，而是放在了1号位置，这样方便我们寻找父节点：
我们可以先测试一下：
#include"heap.h" int main() { Heap<int> heap; heap.insert(12); heap.insert(23); heap.insert(1); heap.insert(0); heap.insert(24); heap.insert(4); heap.insert(188); heap.insert(9); heap.insert(58); heap.printHeap(); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
两种调整算法
向上调整算法
向上调整算法的核心是把每一个结点都当做孩子，去跟自己的父亲比较，如果比自己的父亲大（或者小）交交换数据：
递归版本
递归版本比较好想，我只管我自己和父亲的比较，比较完之后，继续向上比较：
// 向上调整函数（以小根堆为例） // 输入参数：index - 需要进行调整的子节点索引 void sifUpHeap(const size_t& index) { // 如果索引小于 1，说明已经到达根节点或无效索引，无需继续调整，直接返回 if (index < 1) { return; } // 获取当前子节点的父节点索引 size_t parentIndex = Parent(index); // 如果子节点索引大于 1（即不是根节点），并且子节点的值小于其父节点的值 // 则交换两者，确保父节点的值小于其子节点的值（小根堆性质） if (index > 1 && _data[parentIndex] > _data[index]) { std::swap(_data[parentIndex], _data[index]); // 对交换后的新父节点（原子节点）继续进行向上调整，确保整棵子树满足小根堆性质 sifUpHeap(parentIndex); } // 返回，完成当前节点的向上调整过程 return; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
但是我们这样只是完成了一个数据的调整，我们要所有的数据进行调整：
//向上调整算法(以小根堆为例) void sifUpHeap(const size_t& index) { if (index < 1) { return; } if(index > 1 && _data[Parent(index)] > _data[index]) { std::swap(_data[Parent(index)],_data[index]); //接着向上 sifUpHeap(Parent(index)); } return; } //调整为小根堆 void ToMinHeap() { for(int i = 1; i < _size + 1; i++) { sifUpHeap(i); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
非递归版本
我们也可以不用递归，使用迭代来完成：
// 向上调整函数（非递归版本，以小根堆为例） // 输入参数：child - 需要进行调整的子节点索引 void sifUpHeap_non(size_t child) { // 计算当前子节点的父节点索引 size_t parent = child / 2; // 循环迭代，直到子节点成为根节点或已满足小根堆性质 while (child > 1) { // 如果子节点的值小于其父节点的值 // 则交换两者，确保父节点的值小于其子节点的值（小根堆性质） if (_data[Parent(child)] > _data[child]) { std::swap(_data[Parent(child)], _data[child]); // 更新子节点索引为交换后的父节点索引，准备对新的子节点进行下一轮比较 child = parent; // 重新计算父节点索引 parent = child / 2; } else { // 子节点已满足小根堆性质，跳出循环，结束调整 break; } } } //调整为小根堆 void ToMinHeap() { for(int i = 1; i < _size + 1; i++) { sifUpHeap_non(i); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
向下调整算法
向下调整算法是把所有结点当做父亲结点，去和自己的孩子结点比较，看哪个孩子结点比自己大或小，就交换：
向下调整算法有个条件：左右子树必须为堆，因为这个特性，我们向下调整算法得从最后一个有孩子的双亲结点开始：
// 下降调整函数（以小根堆为例） // 输入参数：index - 需要进行调整的父节点索引 void sifDownHeap(const size_t& index) { // 计算当前父节点的左孩子索引 size_t leftchild = LeftChild(index); // 如果左孩子索引超出了堆的有效范围（即不存在左孩子），说明无需调整，直接返回 if (leftchild > _size) { return; // 超出范围，无需调整 } // 初始化 "miner" 为当前父节点的左孩子索引 // "miner" 用于记录待调整子节点中值最小的那个的索引 int miner = leftchild; // 比较左孩子与右孩子（如果存在）的值，确定哪个子节点的值更小 // 如果右孩子存在且其值小于左孩子，更新 "miner" 为右孩子索引 if (index < _size + 1 && _data[leftchild] > _data[leftchild + 1]) { miner++; } // 如果当前父节点的值大于其最小子节点（即 "miner" 所指向的子节点）的值 // 则交换两者，确保父节点的值小于其子节点的值（小根堆性质） if (_data[miner] < _data[index]) { std::swap(_data[miner], _data[index]); // 对交换后的新父节点（原子节点）继续进行向下调整，确保整棵子树满足小根堆性质 sifDownHeap(miner); } // 返回，完成当前节点的向下调整过程 return; } //调整为小根堆 void ToMinHeap() { // for(int i = 1; i < _size + 1; i++) // { // sifUpHeap_non(i); // } for(int i = _size / 2 ; i >=1 ; i--) //从最后一个父节点结点开始调整 { sifDownHeap(i); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
非递归版本
我们也可以用非递归的方式实现：
// 下降调整函数（以小根堆为例） // 输入参数：parent - 需要进行调整的父节点索引 void sifDownHeap_non(size_t parent) { // 计算当前父节点的左孩子索引，假定左孩子为待调整子节点中值最小的一个 int child = LeftChild(parent); // 循环迭代，直到越界 while (child < _size + 1) { // 如果右孩子存在且其值小于左孩子，更新 "child" 为右孩子索引 // 保持 "child" 指向待调整子节点中值最小的那个 if (parent + 1 < _size + 1 && _data[child] > _data[child + 1]) { child++; } // 如果当前父节点的值大于其最小子节点（即 "child" 所指向的子节点）的值 // 则交换两者，确保父节点的值小于其子节点的值（小根堆性质） if (_data[parent] > _data[child]) { std::swap(_data[parent], _data[child]); // 更新父节点索引为交换后的子节点索引，准备对新的子节点进行下一轮比较 parent = child; // 重新计算子节点索引，从新的父节点开始 child = LeftChild(parent); } else { // 子节点已满足小根堆性质，跳出循环，结束调整 break; } } } //调整为小根堆 void ToMinHeap() { // for(int i = 1; i < _size + 1; i++) // { // sifUpHeap(i); // } for(int i = _size / 2 ; i >=1 ; i--) //从最后一个结点开始调整 { sifDownHeap_non(i); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
向上调整算法和向下调整算法的比较
向上调整算法（Sift Up）和向下调整算法（Sift Down）是堆数据结构中常用的两种调整方法，它们各有特点和适用场景，无法简单地说哪个更优秀。选择使用哪种调整方法取决于具体的堆操作需求和上下文。下面分别介绍两者的特性及适用场景：
向上调整算法（Sift Up）：
- 用途：通常用于将新插入的元素或被修改的元素调整到堆中的正确位置，使其满足堆性质（大根堆或小根堆）。例如，在插入新元素后，将其放在堆末尾，然后从该位置开始向上调整，确保新元素及其路径上的所有节点满足堆性质。
- 特点：从堆底部（新元素所在位置或被修改元素所在位置）开始，逐层向上比较父节点与子节点的值，若子节点值更适合堆顶（对于大根堆，子节点值更大；对于小根堆，子节点值更小），则交换二者，直至子节点成为堆顶或已满足堆性质。
优点：- 适用于插入操作和单元素修改后的调整，因为新元素或被修改元素的初始位置已知，可以直接从该位置开始调整。
- 调整过程中涉及的节点数量相对较少，时间复杂度为 O(log n)，效率较高。
缺点：- 不适用于堆顶元素被删除后的调整，因为此时需要重新确定堆顶元素，且可能需要对多个子节点进行比较和调整。
向下调整算法（Sift Down）：
- 用途：通常用于删除堆顶元素后重新调整堆，或在构建堆的过程中对整个堆进行调整。例如，在删除堆顶元素后，将堆末尾元素移至堆顶，然后从堆顶开始向下调整，确保所有节点满足堆性质。
- 特点：从堆顶开始，逐层向下比较父节点与子节点的值，若父节点值更适合堆底（对于大根堆，父节点值更小；对于小根堆，父节点值更大），则交换二者，直至父节点成为堆底或已满足堆性质。
优点：- 适用于堆顶元素被删除后的调整，因为此时堆顶元素已知，可以直接从该位置开始调整。
- 在构建堆的过程中，可以从最后一个非叶子节点开始逐个进行向下调整，确保整个堆满足堆性质。
缺点：- 对于插入操作或单元素修改后的调整，可能需要遍历到堆底才能找到新元素或被修改元素的最终位置，调整过程中涉及的节点数量可能较多。
综上所述，向上调整算法和向下调整算法各有优势，适用于不同的堆操作场景。在实际应用中，根据具体需求选择合适的调整方法，或者结合使用这两种方法，可以有效维护堆数据结构的性质，确保堆操作的高效性。因此，不能简单地说哪个更优秀，而应视具体情况灵活选用。
如果大家阅读完之后还是比较迷糊的话，可以点击这里，这里是我之前写的堆的博客，介绍的更为详细：
整合逻辑
向上调整和向下调整的算法建立大小根堆的逻辑差别不大，所以我整合了这些逻辑写了一个通用性高的：
#pragma once #include<iostream> #include<vector> /* 定义一个泛型堆类模板，该模板允许用户定义堆的特性，包括： - 是否为向上调整（IsUp，默认构造堆时使用） - 是否为最大堆/最小堆（MaxORMin，true 表示最大堆，false 表示最小堆） 此类提供了基本的堆操作，如插入元素、打印堆内容以及整体向上或向下调整堆结构。 */ template<class T,bool IsUp,bool MaxORMin> class myHeap { public: myHeap() :_size(0) { _data.resize(10 + 1); } myHeap(const size_t& size) { _data.resize(size + 1); } //插入 void insert(const T& data) { if(_size > _data.capacity()) { _data.resize(2 * _data.capacity()); } //插入 _data[++_size] = data; } //仿函数 void operator()(size_t index,bool flag,bool BigSmall) { // 根据flag判断是向上调整还是向下调整 //flag = true 向上调整 //flag = false 向下调整 // 根据BigSmall判断是构建最大堆还是最小堆 // BigSmall = true 建立小堆 // BigSmall = false 建立大堆 switch(flag) { case true: //向上调整算法 { switch(BigSmall) { case true: //建立小根堆 { while(true) { if(index == 1) { index++; continue; } size_t otherIndex = index / 2 ; if((otherIndex < 1) || (_data[otherIndex] <= _data[index])) break; std::swap(_data[otherIndex],_data[index]); index = otherIndex; } } break; case false: //建立大根堆 { while(true) { if(index == 1) { index++; continue; } size_t otherIndex = index / 2 ; if((otherIndex < 1) || (_data[otherIndex] >= _data[index])) break; std::swap(_data[otherIndex],_data[index]); index = otherIndex; } } break; } } break; case false: //向下调整算法 { switch (BigSmall) { case true: //建立小根堆 { while(true) { size_t otherIndex = 2 * index; if(otherIndex + 1 < _size + 1 && _data[otherIndex] > _data[otherIndex + 1]) { otherIndex++; } if((otherIndex > _size) || (_data[otherIndex] >= _data[index])) break; std::swap(_data[otherIndex],_data[index]); index = otherIndex; } } break; case false: //建立大根堆 { while(true) { size_t otherIndex = 2 * index; if(otherIndex + 1 < _size + 1 && _data[otherIndex] < _data[otherIndex + 1]) { otherIndex++; } if((otherIndex > _size) || (_data[otherIndex] <= _data[index])) break; std::swap(_data[otherIndex],_data[index]); index = otherIndex; } } break; } } break; } } //打印堆 void printHeap() { for(int i = 1; i < _size + 1; i++) { std::cout<< _data[i] << " "; } std::cout << std::endl; } // 向上调整整个堆，遍历所有节点并逐一应用堆调整操作 void adjustUpWholeHeap() { for (size_t i = 1; i < _size + 1; i++) { operator()(i,IsUp,MaxORMin); // 对索引 i 处的节点应用堆调整 } // 输出调整后的堆结构，仅用于展示 for (int i = 1; i < _size + 1; i++) { std::cout << _data[i] << " "; } std::cout << std::endl; } // 向下调整整个堆，遍历所有节点并逐一应用堆调整操作 void adjustDownWholeHeap() { for (size_t i = _size; i >= 1; i--) { operator()(i,IsUp,MaxORMin); // 对索引 i 处的节点应用堆调整 } // 输出调整后的堆结构，仅用于展示 for (int i = 1; i < _size + 1; i++) { std::cout << _data[i] << " "; } std::cout << std::endl; } //调整 void adjustHeap() { if(IsUp == true) //向上调整 { adjustUpWholeHeap(); } else if(IsUp == false) //向下调整 { adjustDownWholeHeap(); } } private: std::vector<T> _data; size_t _size; };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
#include"HeapSort.h" #include"HeapSort2.h" int main() { myHeap<int,true,false> heap; //用向上调整算法建立大根堆 heap.insert(12); heap.insert(23); heap.insert(1); heap.insert(0); heap.insert(24); heap.insert(4); heap.insert(188); heap.insert(9); heap.insert(58); heap.printHeap(); heap.adjustHeap(); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/935021?site
推荐阅读
相关标签
