树的初阶相关知识（中）

https://blog.csdn.net/qscftqwe/article/details/155913644

这是上节课的链接，大家可以点进去看一下！

一.堆的实现

关于堆这部分，其实只需要搞明白向上建堆和向下建堆动即可，这两部分是堆的重难点，至于其它的我就不和大家讲解了。

typedef int HPDataType; class Heap { private: size_t _size;//堆的有效数据 size_t _capacity;//堆的容量 HPDataType* _array;//数组指针 static size_t _npos;//防止溢出 }; size_t Heap::_npos = -1;

这是相关的成员变量，大家看一下即可。

二.向上建堆

// 堆的插入 void HeapPush(HPDataType x) { if (_size != _capacity) { _array[_size++] = x; AdjustUp(); } else { std::cout << "堆已满，需要先删除数据" << std::endl; } } // 向上建堆 void AdjustUp() { size_t child = _size - 1;//子节点位置 size_t parent = (child - 1) / 2;//父节点位置 while (child > 0) { if (_array[child] > _array[parent])//孩子大于父节点 { std::swap(_array[parent], _array[child]);//交换孩子和父节点 child = parent; parent = (child - 1) / 2;//往上浮和上面继续比较 } else { break; } } }

向上建堆，是堆插入的重要实现函数，下面我将讲解向上建堆的相关知识。

我们向上建堆的时候，我们要插入的地方是已经符合堆的规则的，也就是说我们要新插入这个元素是需要继续维护堆的性质的，我们拿大堆举例。现在我们要插入一个9那么该这么处理呢？

首先图中9这个元素就是我们要插入的新元素，首先我们知道大堆的性质就是父大于子，那么如果我们插入的这个元素比父亲大，那么是不是需要更换一下呀！

size_t child = _size - 1;//当前位置 size_t parent = (child - 1) / 2;//父节点位置 if (_array[child] > _array[parent])//孩子大于父节点 { std::swap(_array[parent], _array[child]);//交换孩子和父节点 }

那么代码的实现就应该是这样，首先我们要找到父节点的位置，然后拿父节点和子节点比较。至于新插入的节点是child-1，是因为我是先执行这个代码_array[_size++] = x，然后再向上建堆因此要-1，至于为什么parent的位置是（child-1）/ 2，这就关于完全二叉树的相关知识。

执行完代码的结果是这样的，你发现还是不符合堆的性质，因为9（孩子）> 8（父亲），那我们是不是需要继续和父亲进行比较，那么是不是就需要用到循环。

while (child > 0) { if (_array[child] > _array[parent])//孩子大于父节点 { std::swap(_array[parent], _array[child]);//交换孩子和父节点 pos = parent; parent = (child - 1) / 2;//往上浮和上面继续比较 } }

那么相关代码就是 child= parent; parent = (child - 1) / 2;这两行，分别是更新孩子节点和父节点。那么至于循环条件为什么是child>0呢？

其实很简单，因为如果孩子是根节点，那么它是没有父节点，既然没有父节点还这么进行比较呢，因此child>0就是我们循环条件终止。

其实大家看完这个代码发现是没有扩容的，至于我为什么没有加扩容，其实我是这么想的，堆的重点是向上建堆和向下建堆这两个是堆的核心，至于其他核心操作其实就是根据这两个进行的，因此我们重点是学习这两个核心。说到底还是我想偷懒了，不好意思哈！

三.向下建堆

说完了向上建堆，我们又来认识一下向下建堆。首先如果说向上建堆是子去和父比（即：子为主动，父为被动）那么向下建堆就是父去和子比（即：父为主动，子为被动）

// 堆的删除 void HeapPop() { assert(!HeapEmpty());//不能为空 std::swap(_array[0], _array[_size - 1]);//交换第一个和最后一个元素 _size--; AdjustDown(0); } // 向下建堆 void AdjustDown(size_t parent) { size_t child = parent * 2 + 1;//左孩子 while (child < _size) { if (child + 1 < _size && _array[child + 1] > _array[child]) { ++child;//右孩子更大 } if (_array[parent] < _array[child])//父节点小于最大孩子 { std::swap(_array[parent], _array[child]);//交换大孩子和父节点 parent = child; child = parent * 2 + 1;//往下浮和下面继续比较 } else { break;//已满足堆的性质 } } }

在解释向下建堆之前，我们先了解一下什么情况我们会用到向下建堆，那么必然是删除了，那堆的删除是这么删的呢？

通过图片我们可以知道，堆的删除是把根节点和最后一个节点进行调换，然后只需要把最后一个节点删除即可（此时最后一个节点指的是根节点），在做完这个动作后我们发现该堆不符合大堆，因此我们是不是需要用到向下建堆呀！

首先我们先获取左孩子，然后拿它去和有效字符个数去比，确保它不越界。然后下一步就是我们要去比较左孩子和右孩子那一个大，注意这个步骤是需要判断右孩子是否为空的，避免越界错误！

然后我们拿父节点和较大子节点比，如果父节点<较大的子节点，那么是不是要交换位置！

交换完，你发现还是不符合堆的性质，那是不是就和向上建堆遇到的情况，因此我们是不是需要继续更新父节点和子节点的位置。

其实向上建堆和向下建堆的最大区别就是在更新父节点和子节点的顺序下，向上就是先更新子节点，然后再更新父节点，向下建堆就是反过来的！

四.堆的初始化

什么叫堆的初始化呢，就是我们直接把一个数组转换成堆，那么该如何转换呢？

首先我们需要找到最后一个带有左孩子的父节点，这个很简单就是求数组最后一个节点的父亲即可，然后从该节点一直到根节点都采取向下建堆即可！

// 堆的初始化 size_t pos = (n - 1) / 2;//找到最后一个非叶子节点且它至少有左孩子 for (size_t i = pos; i != _npos; i--) { AdjustDown(i); }

为什么要这样弄呢，是因为之所以一个数组不符合堆的性质，必然是因为有一颗小树不符合堆的性质，那如果这样分析一颗小树不符合堆的性质其必然是父节点和子节点的关系有问题，因此我们只要改变父节点和子节点的关系即可！

那为什么要从最后一个带有左孩子的父节点开始找起，直至根节点。不能反过来吗？

因为如果从根节点开始向下调整，可能破坏已调整好的子树！

然后就是堆的初始化我们为什么要用向下建堆，不可以用向上建堆吗？

关于这个问题我们后面的章节再给大家带来为什么！

五.堆的完整实现代码

#pragma once #include<iostream> #include<assert.h> typedef int HPDataType; //创建大堆 class Heap { public: Heap() :_size(0) ,_capacity(10) ,_array(new HPDataType[_capacity]) {} // 堆的构建 Heap(HPDataType* a, size_t n) :_size(n) , _capacity(n > 0 ? n * 2 : 10)//相当于开双倍容量 ,_array(new HPDataType[_capacity]) { if (n > 0)//避免为空 { for (size_t i = 0; i < n; i++)//拷贝数据 { _array[i] = a[i]; } // 堆的初始化 size_t pos = (n - 1) / 2;//找到最后一个非叶子节点且它至少有左孩子 for (size_t i = pos; i != _npos; i--) { AdjustDown(i); } } } // 堆的销毁 ~Heap() { delete[] _array; _array = nullptr; _size = _capacity = 0; } // 向下建堆 void AdjustDown(size_t parent) { size_t child = parent * 2 + 1;//左孩子 while (child < _size) { if (child + 1 < _size && _array[child + 1] > _array[child]) { ++child;//右孩子更大 } if (_array[parent] < _array[child])//父节点小于最大孩子 { std::swap(_array[parent], _array[child]);//交换大孩子和父节点 parent = child; child = parent * 2 + 1;//往下浮和下面继续比较 } else { break;//已满足堆的性质 } } } // 向上建堆 void AdjustUp() { size_t child = _size - 1;//当前位置 size_t parent = (child - 1) / 2;//父节点位置 while (child > 0) { if (_array[child] > _array[parent])//孩子大于父节点 { std::swap(_array[parent], _array[child]);//交换孩子和父节点 child = parent; parent = (child - 1) / 2;//往上浮和上面继续比较 } else { break; } } } // 堆的插入 void HeapPush(HPDataType x) { if (_size != _capacity) { _array[_size++] = x; AdjustUp(); } else { std::cout << "堆已满，需要先删除数据" << std::endl; } } // 堆的删除 void HeapPop() { assert(!HeapEmpty());//不能为空 std::swap(_array[0], _array[_size - 1]);//交换第一个和最后一个元素 _size--; AdjustDown(0); } // 取堆顶的数据 HPDataType HeapTop()const { assert(!HeapEmpty());//不能为空 return _array[0]; } // 堆的数据个数 size_t HeapSize()const { return _size; } // 堆的判空 bool HeapEmpty()const { return _size == 0; } private: size_t _size;//堆的有效数据 size_t _capacity;//堆的容量 HPDataType* _array;//数组指针 static size_t _npos;//防止溢出 }; size_t Heap::_npos = -1;

好了今天的内容就讲到这里吧，我们今天的重点是讲解用完全二叉树的思想实现的一种数据结构类型堆，而堆的实现重点其实是再向上建堆和向下建堆这两个概念，关于堆还有一个重难点的知识就是为什么堆的初始化我们用的是向下建堆！