数据结构——堆,堆排序

avatar
作者
筋斗云
阅读量:4

前提

我们都知道内存分布中的堆区(Heap section)new出来的空间都在堆区上。和堆区有一个名字很相近的数据结构——堆(Heap),虽然名称相近,但两者是完全不同的东西。

因为十大排序算法中有一个堆排序,所以从头开始了解下这个数据结构, 终学习下堆排序算法

堆——数据结构

堆是什么

堆的本质是完全二叉树,只不过要在完全二叉树上加一些限制条件。根据加的限制条件的不同,堆又被分为大顶堆小顶椎

大顶堆

大顶堆:任意节点的值>=其子节点的值。
如下所示:
在这里插入图片描述

小顶堆

小顶堆:任意节点的值<=其子节点的值。
如下所示:
在这里插入图片描述

堆的实现

接下来我们实现一个大顶堆。

堆的存储与表示

堆的本质是完全二叉树,树形结构可以使用数组链表进行存储。但是对于完全二叉树来说,使用数组存储更为合适。为什么呢?接下来做个简单分析。
在这里插入图片描述
如果使用数组进行存储,头节点放在数组中下标为0的位置,剩于的所有节点顺序在数组中存放。
这样当我们访问下标为i的结点时:

  • 可以使用2i+i访问它的左子节点
  • 使用2i+2访问它的右子节点
  • 使用 (i-1)/2 访问它的节点
  • 同时,如果计算出的下标大于数组的容量,代表没有此节点

访问堆顶元素

我们知道对于堆来说,堆顶元素存储在数组的0号下标,所以直接返回即可。

元素入堆

要给堆添加元素时,添加的元素可能会破坏堆的成立条件 (对于大顶堆,任意节点的值>=其子节点的值) 。因此添加元素到堆底后,我们要调整堆中节点的位置。

那么一个简单的思路是:比较插入节点与其父节点的值,如果插入节点更大,则将它们交换。然后继续执行此操作,从底至顶修复堆中的各个节点,直至越过根节点或遇到无须交换的节点时结束。

这里最坏的清况是:插入的节点是新的根节点。所以如果整个堆有 n n n 个节点,二叉树高 O ( l o g n ) O(logn) O(logn),此时的时间复杂度为 O ( l o g n ) O(logn) O(logn)。最好的清况是:插入的节点不需要移动。此时的时间复杂度为 O ( 1 ) O(1) O(1)

堆顶元素出堆

堆顶元素出堆后,新的堆顶元素是谁?而且由于堆中少了一个元素,所以堆中剩于元素在数组中的索引会发生变化,所以如何确定新的元素索引呢?

这里的算法为:

  1. 交换堆顶元素与堆底元素(交换根节点与最右叶节点)。
  2. 交换完成后,将堆底从列表中删除(注意,由于已经交换,因此实际上删除的是原来的堆顶元素)。
  3. 从根节点开始,从顶至底执行堆化。

实现代码

#include <iostream> #include <vector>  template <typename T> class Heap { public:   Heap() = default;    T peek() { /* Get the top element of the heap */     if (data.empty())       throw std::runtime_error("Heap is empty");     return data[0];   }    void push(T val) { /* Insert an element into the heap */     data.push_back(val);     siftUp(data.size() - 1);   }    void pop() { /* Remove the top element of the heap */     if (data.empty()) {       throw std::runtime_error("Heap is empty");     }      std::swap(data[0], data[data.size() - 1]);     data.pop_back();     siftDown(0);   }    int size() { return data.size(); }  private:   std::vector<T> data;    inline int left(int i) { return 2 * i + 1; }     // Get the left child of i   inline int right(int i) { return 2 * i + 2; }    // Get the right child of i   inline int parent(int i) { return (i - 1) / 2; } // Get the parent of i    void siftUp(int i) {                           // Move the element up the heap     while (i > 0 && data[parent(i)] < data[i]) { /* Compare with the parent */       std::swap(data[parent(i)], data[i]);       i = parent(i);     }   }    void siftDown(int i) { // Move the element down the heap     while (true) {       int l = left(i), r = right(i), ma = i;       if (l < data.size() && data[l] > data[ma]) {         ma = l;       }       if (r < data.size() && data[r] > data[ma]) {         ma = r;       }       std::swap(data[i], data[ma]);       if (ma == i) {         break;       }       i = ma;     }   } };  int main() {   Heap<int> heap;    heap.push(1);   heap.push(2);   heap.push(3);   heap.push(4);   heap.push(5);    std::cout << "Heap size: " << heap.size() << std::endl;   std::cout << "Heap top: " << heap.peek() << std::endl;    heap.pop();    std::cout << "Heap size: " << heap.size() << std::endl;   std::cout << "Heap top: " << heap.peek() << std::endl; } 

优先队列

堆通常可以用来实现优先队列,优先队列(Priority Queue)是一种抽象数据类型,类似于普通的队列或堆栈数据结构,但每个元素都有一个优先级优先级高的元素会优先出队(被处理),而不是按照元素入队的顺序来处理。

堆排序

如果你明白上面的内容后,那么堆排序就比较简单了。
流程如下:

  1. 将给定的无序数组建成一个堆(假定是大顶堆)
  2. 将堆顶元素弹出
  3. 重新对堆中剩于的元素堆化
  4. 重复2和3,直到堆中无元素

这里存在一个问题:如何将给定的无序数组建成一个堆?
一个很笨的方法是:我们将无序数组中的元素一个一个取出来,然后push到堆中。伪代码如下:

  std::vector<int> vec{1, 3, 5, 2, 0, 4};   Heap<int> heap;   for (int i = 0; i < vec.size(); i++) {     heap.push(vec[i]);   } 

如果有 n n n个节点的话,这里的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)


参考链接2,有一个时间复杂度为 O ( n ) O(n) O(n)的建堆方法。

堆排序代码

简单思路版本:

/* 堆的长度为 n ,从节点 i 开始,从顶至底堆化 */ void siftDown(std::vector<int> &nums, int n, int i) {   while (true) {     // 判断节点 i, l, r 中值最大的节点,记为 ma     int l = 2 * i + 1;     int r = 2 * i + 2;     int ma = i;     if (l < n && nums[l] > nums[ma])       ma = l;     if (r < n && nums[r] > nums[ma])       ma = r;     // 若节点 i 最大或索引 l, r 越界,则无须继续堆化,跳出     if (ma == i) {       break;     }     // 交换两节点     std::swap(nums[i], nums[ma]);     // 循环向下堆化     i = ma;   } }  /* 堆排序 */ std::vector<int> heapSort(std::vector<int> &nums) {   // 建堆操作:堆化除叶节点以外的其他所有节点   for (int i = nums.size() / 2 - 1; i >= 0; --i) {     siftDown(nums, nums.size(), i);   }   std::vector<int> res; /* 用来收集堆顶元素 */   // 从堆中提取最大元素   for (int i = nums.size() - 1; i >= 0; --i) {     // 交换根节点与最右叶节点(交换首元素与尾元素)     std::swap(nums[0], nums[nums.size() - 1]);     res.push_back(nums.back());     nums.pop_back(); // 将堆顶元素弹出     siftDown(nums, nums.size(), 0);  // 重新对堆中剩于的元素堆化   }   return res; }  int main() {   std::vector<int> vec{1, 3, 5, 2, 0, 4};   std::vector<int> res = heapSort(vec);    for (int i = 0; i < res.size(); i++) {     std::cout << res[i] << " ";   } } 

上面的这种写法要多定义一个空间复杂度为 O ( n ) O(n) O(n)的结果数组,用来保存结果,这会造成额外的空间浪费。

那么有没有方法可以建堆后,直接对进行排序。

答案是有的,每次将堆的顶点和堆底交换后,顶点元素本是要弹出的(目的是对剩于的堆中的元素重新进行排序)。我们可以弹出操作变为动态减少堆的大小。代码如下:

/* 堆的长度为 n ,从节点 i 开始,从顶至底堆化 */ void siftDown(std::vector<int> &nums, int n, int i) {   while (true) {     // 判断节点 i, l, r 中值最大的节点,记为 ma     int l = 2 * i + 1;     int r = 2 * i + 2;     int ma = i;     if (l < n && nums[l] > nums[ma])       ma = l;     if (r < n && nums[r] > nums[ma])       ma = r;     // 若节点 i 最大或索引 l, r 越界,则无须继续堆化,跳出     if (ma == i) {       break;     }     // 交换两节点     std::swap(nums[i], nums[ma]);     // 循环向下堆化     i = ma;   } }  /* 堆排序 */ void heapSort(std::vector<int> &nums) {   // 建堆操作:堆化除叶节点以外的其他所有节点   for (int i = nums.size() / 2 - 1; i >= 0; --i) {     siftDown(nums, nums.size(), i);   }    // 从堆中提取最大元素,循环 n-1 轮, because the last element is the smallest   for (int i = nums.size() - 1; i > 0; --i) {     // 交换根节点与最右叶节点(交换首元素与尾元素)     std::swap(nums[0], nums[i]);     siftDown(nums, i, 0); // every loop, the heap size is reduced by 1   } }  int main() {   std::vector<int> vec{1, 3, 5, 2, 0, 4};   heapSort(vec);    for (int i = 0; i < vec.size(); i++) {     std::cout << vec[i] << " ";   } } 

所以堆排序的时间复杂度应为 O ( n l o g n ) O(nlogn) O(nlogn),因为for循环n-1次,每一次堆化的复杂度为 O ( l o g n ) O(logn) O(logn)

参考链接

  1. https://www.hello-algo.com/chapter_heap/heap/#3
  2. https://www.hello-algo.com/chapter_heap/build_heap/

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!