哈尔滨公司网站开发,城阳网站建设公司电话,一键logo设计网,网站建设 400电话 广告语堆的实现 概念实现完整代码 概念
介绍堆之前得说一下二叉树#xff0c;因为堆的逻辑结构是二叉树#xff0c;二叉树的树的子集#xff0c;树只有一个根节点#xff0c;向下衍生出了很多节点#xff0c;并且这个节点之间相互没有连接#xff0c;除非是父子节点#xff0… 堆的实现 概念实现完整代码 概念
介绍堆之前得说一下二叉树因为堆的逻辑结构是二叉树二叉树的树的子集树只有一个根节点向下衍生出了很多节点并且这个节点之间相互没有连接除非是父子节点如果有连接了那就是图如果拥有很多独立不连接的树这样的数据结构称之为森林。 如果对树作进一步的限制每一个节点包括根节点最多只有两个子树那么这样的树叫做二叉树比如 这种也是
二叉树呢又可以分为完全二叉树和满二叉树 完全二叉树就是每一个节点都有两个子树子节点例如
满二叉树就是除了最后一层也就是最底下的一层其他的每层都是完全二叉树并且最后一层的节点得从左到右存在下面这种就属于满二叉树
但是这种就不属于满二叉树 堆的逻辑数据结构就是使用满二叉树实现的为什么说是逻辑呢这是因为我们在实际实现的时候使用的是数组来实现的原因如下: 如果我们想使用数组来存储下面这个二叉树
这样对吗像这样写的话岂不是没有二叉树的特点了比如怎么判断左右子树呢所以我们得从上到下从左到右的添加进数组。 例如 这样就可以轻松知道左右子树从而通过数组构建出二叉树了但是这个数组的中间浪费了不少空间如何避免呢 那就是使用满二叉树。
数组中的任意一个节点怎么能够得到他的左右子节点和父节点呢可以通过下面的几个公式 如果想知道数组arr里面的节点i的左右子节点和父节点
父节点arr[(i-1)/2]左节点arr[i*21];右节点arr[i*22];
概念说完了我们接下来可以用这种数据结构来构建一个大堆和小堆大堆的特点是父节点一定大于子节点但是左右节点没有讲究小堆则相反。 利用大小堆可以实现topk问题也就是求出一堆数据中第几大小的数是哪一个。也可以实现堆排序。
实现
先实现一个大堆
然后就得插入数据 每次插入数据都是插入到数组的最后面也就是二叉树的最下一层的最右边此时需要维护大堆的规则也就是父节点的值大于子节点的值由于每次插入时都是在最下面所以如果不符合规则当前插入的值大于父节点我们就利用adjustUp函数进行向上调整。如下
void Heap::adjustUp()
{int curIndex _heap.size() - 1;while (curIndex 0){int parentIndex (curIndex - 1) / 2;if (_heap[parentIndex] _heap[curIndex]){std::swap(_heap[parentIndex], _heap[curIndex]);curIndex parentIndex;}else{break;}}}写一下测试跑跑看吧
#include heap.hint main() {Heap heap;heap.insert(1);heap.insert(2);heap.insert(3);
}
喔吼拿不到数组的值我们要得到堆顶的值那就写一个吧
int Heap::top()
{if (_heap.size() 0){return _heap[0];}}运行得到 可以看到堆顶的数据3数组下标0处的数据是3可以我们在插入的时候0处一开始插入的是1但是结果是3这就说明没有问题。
如果要实现topk问题我们需要每次都将堆顶的元素给删除了如果求第3大的数我们就删除两次然后此时堆顶的元素就是第3大的数了下面我们来实现删除功能
在数组中如果直接删除下标0处的元素在进行调整这样会需要变动整个数组效率低下因此我们选择将下标0处的元素与最后一个元素交换然后直接删除最后一个元素在进行向下调整即可
void Heap::pop()
{if (_heap.size() 0){std::swap(_heap[0], _heap[_heap.size() - 1]);_heap.pop_back();adjustDown();}
}void Heap::adjustDown()
{int size _heap.size();int curIndex 0, leftIndex 1;while (leftIndex size){if (leftIndex 1 size _heap[leftIndex] _heap[leftIndex 1]){leftIndex;}if (_heap[curIndex] _heap[leftIndex]){std::swap(_heap[curIndex], _heap[leftIndex]);curIndex leftIndex;leftIndex curIndex * 2 1;}else{break;}}}在adjustDown这个函数中利用leftIndex 1 size _heap[leftIndex] _heap[leftIndex 1]来判断左右节点哪一个更大一些然后用较大值和父节点的值进行比较如果父节点的值小于子节点的值那么就要向下调整也就是需要交换之后更新当前的父节点和左节点再次进行判断。
下面进行测试 结果也没有问题。
然后我们根据这个进行堆排序的编写 测试代码如下
int main() {srand((unsigned int)time(NULL));std::vectorint v;for (int i 0; i 100; i){v.push_back(rand()%100);}Heap heap;heap.sort(v);for (auto e : v){std::cout e ;}
}结果也没有问题。
完整代码
//heap.h
#pragma once
#include vector
#include iostream
#include cassertclass Heap {
public:Heap();~Heap();void insert(int value);void adjustUp();int top();void pop();void adjustDown();void sort(std::vectorint v);
private:std::vectorint _heap;
};//heap.cpp
#include heap.hHeap::Heap()
{}Heap::~Heap()
{}void Heap::insert(int value)
{_heap.push_back(value);adjustUp();
}void Heap::adjustUp()
{int curIndex _heap.size() - 1;while (curIndex 0){int parentIndex (curIndex - 1) / 2;if (_heap[parentIndex] _heap[curIndex]){std::swap(_heap[parentIndex], _heap[curIndex]);curIndex parentIndex;}else{break;}}}int Heap::top()
{if (_heap.size() 0){return _heap[0];}}void Heap::pop()
{if (_heap.size() 0){std::swap(_heap[0], _heap[_heap.size() - 1]);_heap.pop_back();adjustDown();}
}void Heap::adjustDown()
{int size _heap.size();int curIndex 0, leftIndex 1;while (leftIndex size){if (leftIndex 1 size _heap[leftIndex] _heap[leftIndex 1]){leftIndex;}if (_heap[curIndex] _heap[leftIndex]){std::swap(_heap[curIndex], _heap[leftIndex]);curIndex leftIndex;leftIndex curIndex * 2 1;}else{break;}}}void Heap::sort(std::vectorint v)
{for (int i 0; i v.size(); i){insert(v[i]);}for (int i 0; i v.size(); i){v[i] top();pop();}
}//main.c
#include heap.h
#include ctimeint main() {/*Heap heap;heap.insert(1);heap.insert(2);heap.insert(3);heap.pop();std::cout heap.top() std::endl;heap.pop();std::cout heap.top() std::endl;*/srand((unsigned int)time(NULL));std::vectorint v;for (int i 0; i 100; i){v.push_back(rand()%100);}Heap heap;heap.sort(v);for (auto e : v){std::cout e ;}
}新人创作不易你的点赞和关注都是对我莫大的鼓励再次感谢您的观看。
