锐客网

  1. 首页 > it技术 > >

C++|Data Structures in C++（堆和堆排序）

c++堆排序堆数据结构


文章目录

  • 堆
  • 堆的代码实现
  • 堆排序
  • C++11 中的堆 priority_queue

堆 堆 Heap 这种数据结构其实就是一颗 “完全二叉树”，每个节点的值总是不大于或不小于其父节点的值：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。一棵深度为k且有 个结点的二叉树称为 “满二叉树”。
C++|Data Structures in C++（堆和堆排序）
文章图片

堆的分类：
  • 大顶堆：每个节点的值都大于或等于其子节点的值
  • 小顶堆：每个节点的值都小于或等于其子节点的值
    C++|Data Structures in C++（堆和堆排序）
    文章图片
大顶堆和小顶堆都可以用来“从小到大”或“从大到小”排序，一般使用大顶堆。
堆的代码实现 堆就是一颗完全二叉树，中间没有空洞，因此可以使用内存连续的数组或动态数组来实现。以大顶堆为例。
先将堆中结点的序号和数组索引进行对应：（与层次遍历类似）
C++|Data Structures in C++（堆和堆排序）
文章图片

显然，每对父子结点在数组中的索引存在数学关系：
  • 索引为t t t 的结点，其父结点索引为( t ? 1 ) / 2 (t-1)/2 (t?1)/2
  • 索引为t t t 的结点，其左孩子索引为t × 2 + 1 t×2+1 t×2+1，右孩子索引为t × 2 + 2 t×2+2 t×2+2
插入操作：push
  • 先将元素插入到最后一个结点
  • 由此逐层向上渗透：若比父结点大，就交换
    C++|Data Structures in C++（堆和堆排序）
    文章图片
删除操作：pop
  • 先将根节点删除，替换为最后一个结点
  • 由此逐层向下渗透：若比左右结点小，就和bigger交换
    C++|Data Structures in C++（堆和堆排序）
    文章图片
模板类代码：
#pragma once #include template class MaxHeap { public: MaxHeap() {} ~MaxHeap() {} void push(T& x); void pop(); bool empty() const; const T& top() const; //private: std::vector heap; }; template inline void MaxHeap::push(T& x) { // 添加元素 heap.push_back(x); // 向上渗透 int index = heap.size() - 1; while (index > 0) { int parent = (index - 1) / 2; if (heap[parent] >= x) break; heap[index] = heap[parent]; index = parent; } heap[index] = x; }template inline void MaxHeap::pop() { // 替换根结点 T x = heap[0] = heap[heap.size() - 1]; heap.pop_back(); if (heap.empty()) return; // 向下渗透 int index = 0; while (index * 2 + 1 < heap.size()) // 左子结点存在 { int larger_child; int l_child = index * 2 + 1; int r_child = index * 2 + 2; if (r_child < heap.size() && heap[r_child] >= heap[l_child])// 右子结点存在 { larger_child = r_child; } else { larger_child = l_child; } if (x > heap[larger_child])// 截止 break; heap[index] = heap[larger_child]; index = larger_child; } heap[index] = x; }template inline bool MaxHeap::empty() const { return heap.empty(); }template inline const T& MaxHeap::top() const { return heap[0]; }

堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏、最好、平均时间复杂度均为O(nlogn)，是不稳定排序。
基本思想：
  1. 构造一个空的大顶堆；
  2. 将待排序序列push进入大顶堆，此时，整个序列的最大值就是堆顶的根节点
  3. 将大顶堆的根节点反复读出、删除即得到有序序列
堆排序测试代码：
#include #include "MaxHeap.h"using namespace std; int main(int argc, char* argv[]) { int a[10] = { 11,3,25,177,299,0,52,74,86,308 }; int n = 10; MaxHeap heap; for (auto x : a) { heap.push(x); }cout << "从小到大："; for (int i = n-1; i >=0; i--) { a[i] = heap.top(); heap.pop(); }//cout << "从大到小："; //for (int i = 0; i < n; i++) //{ //a[i] = heap.top(); //heap.pop(); //} // 输出排序结果 for (int i = 0; i < n; i++) cout << a[i] << ", "; cout << endl; return 0; }

C++11 中的堆 priority_queue 优先队列是一种容器适配器，默认第一个元素总是保持最大，内部类似于堆结构。提供常数时间的最大元素（默认）查找，对数代价的插入与删除(二分法)。
成员函数：
  • top 访问队头元素
  • empty 队列是否为空
  • size 返回队列内元素个数
  • push 插入元素到队尾 (并排序)
  • emplace 原地构造一个元素并插入队列(并排序)
  • pop 弹出队头元素
  • swap 交换内容
定义：
priority_queue
  • Type 就是数据类型
  • Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）
  • Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入
这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。
【C++|Data Structures in C++（堆和堆排序）】小顶堆定义：
priority_queue < int, vector, greater > q;

    推荐阅读


    上一篇：单片机系列|嵌入式STM32开发中关键字_IO

    下一篇：c++堆排序和堆