专栏首页光城(guangcity)C++那些事之手写二叉堆强化模板函数及比较操作

C++那些事之手写二叉堆强化模板函数及比较操作

C++那些事之手写二叉堆强化模板及比较操作

强化算法、熟练C++

本节重点带大家一起写一个二叉堆,并基于二叉堆实现优先队列,同时练习C++的模板类以及比较操作。

本文的代码后续会放在《C++那些事》仓库中,请持续关注!

https://github.com/Light-City/CPlusPlusThings

1.Heap实现

类模板,二叉堆中需要元素进行比较,二叉堆分为大顶堆与小顶堆,我们通过模板实现支持多种元素类型且支持两种堆的一个Heap类。

在C++中实现,就是下面的模板类,T代表元素类型,Cmp代表可比较对象,我们默认以less,也就是在下面我们将支持默认的小根堆,如果想要支持大根堆,自己传入一个比较对象即可,后面一步步来阐述。

namespace lightcity {
template<typename T,typename Cmp = std::less<T>>
class Heap {
  private:
    vector<T> data_;
    Cmp cmp;
  public:
    Heap() {}
    Heap(T capacity) {
      data_ = vector<T>(capacity);
    }
};
};
  1. 子结点与父结点

二叉堆这里实现我们以vector作为底层,我们数组的index范围为0~index-1。

堆顶就是0。左孩子是1,右孩子是2,依次类推。

我们需要直到当前结点的左孩子与右孩子,父亲是谁?

int GetParent(int child) {
  assert(child > 0);
  return (child - 1)/2;
}
int GetLeftChild(int parent) {
  return 2*parent + 1;
}
int GetRightChild(int parent) {
  return 2*parent + 2;
}

2)Heapify操作

给定一个数组,将数组转为二叉堆(大或小根堆)。

具体实现:从最后一个非叶结点开始,依次向上直到根结点,进行siftdown操作,也就是下沉操作,这样做的目的是,以小根堆为例:当非叶子结点比后面两个孩子大,我们就需要将孩子中最小的结点与之交换,使得满足小根堆性质。

Heap(vector<T>& heap) {
  data_ = heap;
  T last_not_leaf = GetParent(data_.size() - 1);
  while (last_not_leaf >= 0) {
    SiftDown(last_not_leaf);
    last_not_leaf--;
  }
}
  1. SiftDown操作

将非叶子结点下沉,使得满足二叉堆性质。

void SiftDown(int k) {
    while (GetLeftChild(k) < data_.size()) {
        int j = GetLeftChild(k);
        if (j + 1 < data_.size() && cmp(data_[j + 1],data_[j]))
           j =GetRightChild(k); //j++
        // data[j]是此时leftChild 和 rightChild中的最大值
        if (cmp(data_[k],data_[j])) break;
        swap(k, j);
        k = j;
    }
}

swap操作:

void swap(int i, int j) {
  T t = data_[i];
  data_[i] = data_[j];
  data_[j] = t;
}
  1. Pop操作

通过pop操作,我们将堆顶元素删除,具体操作如下:

堆顶与最后一个叶子结点交换,此时最后一个元素便是堆顶,将其删除即可,堆堆顶元素进行SiftDown操作,使其满足二叉堆性质。

void Pop() {
  swap(0,data_.size()-1);
  data_.pop_back();
  SiftDown(0);
}
  1. Push操作

通过Push操作,往堆中添加元素,具体操作如下:

直接将元素在数组尾巴插入,随后从刚才插入的结点开始进行进行SiftUp操作,使得满足二叉堆性质。

void Push(T value) {
  data_.push_back(value);
  SiftUp(data_.size() - 1);
}
  1. SiftUp操作

将元素进行上浮,使得满足二叉堆性质,例如:当前叶子结点是10父亲结点时8,此时不满足大根堆性质,我们就需要交换两者,不断往上,直到当前结点比父亲结点小。

void SiftUp(int k) {
  while (k > 0 && cmp(data_[k], data_[GetParent(k)])) {
    int p = GetParent(k);
    swap(p,k);
    k = p;
  }
}
  1. Top操作

为了方便拿到最大或者最小元素,提供Top接口:

T Top() {
  assert(data_.size() > 0);
  return data_[0];
}
  1. 其他常用操作

最后,就是一些其他的常见操作,例如:元素个数、是否为空等.

int GetSize() {
  return data_.size();
}
void GetData(vector<T> &data) {
  data = data_;
}
bool Empty() {
  return data_.empty();
}

2.优先队列

接着,我们以上述实现的Heap来实现一个优先队列:

namespace lightcity {
template<typename T,typename Cmp = std::less<T>>
class priority_queue {
  private:
    Heap<T, Cmp> heap;
  public:
    priority_queue() {}
    int GetSize() {
        return heap.GetSize();
    }

    void Push(T value) {
        heap.Push(value);
    }

    T Top() {
        return heap.Top();
    }

    void Pop() {
        heap.Pop();
    }

    bool Empty()  {
        return heap.Empty();
    }
};
};

实现简单的很,我们方法都模拟真实的STL中的函数,开头改为大写,记得加namespace,否则编译器模糊不知道调用哪一个。

3.测试

3.1 Heap测试

Heap小根堆例子:

   5
  4    6
0  10

小根堆:

   0
 4   6
5 10

push -1

   0
 4    6
5 10  -1

调整:

   -1
 4     0
5 10 6

测试输出:

小根堆
0 4 6 5 10 
push
-1 4 0 5 10 6 

Heap大根堆例子:

   5
  4    6
0  10

调整堆后:

   10
  5    6
0  4

push 100:

   10
  5    6
0  4  100

调整堆后:

   100
  5    10
0  4  6

输出:

大根堆
10 5 6 0 4 
push
100 5 10 0 4 6 

对应代码:

void HeapTest(bool flag = true) {

  vector<int> data{5,4,6,0,10};
  using namespace lightcity;
  if (flag) {
    cout << "小根堆" << endl;
    Heap<int,CmpMin> heap(data);
    heap.GetData(data);
    for (const auto& elem : data)
      cout << elem <<  " ";
    cout << endl;
    cout << "push" << endl;
    heap.Push(-1);
    heap.GetData(data);
    for (const auto& elem : data)
      cout << elem <<  " ";
    cout << endl;
  }  else {
    cout << "大根堆" << endl;
    Heap<int,CmpMax> heap(data);
    heap.GetData(data);
    for (const auto& elem : data)
      cout << elem <<  " ";
    cout << endl;
    cout << "push" << endl;
    heap.Push(100);
    heap.GetData(data);
    for (const auto& elem : data)
      cout << elem <<  " ";
    cout << endl;
  }

}

3.2 优先队列测试

我们以leetcode347 topk题目测试:

using namespace lightcity;
using pii = pair<int,int>;
class cmp {
public:
    bool operator ()(const pii& a,const pii& b) {
        return a.first<b.first;
    }
};
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

        priority_queue<pii,cmp> pq;
        unordered_map<int,int> um;

        for (auto& num : nums) um[num]++;

        for (auto& elem : um) {
            if (k>0) {
                pq.Push(make_pair(elem.second,elem.first));
                k--;
            } else if (elem.second > pq.Top().first) {
                pq.Pop();
                pq.Push(make_pair(elem.second,elem.first));
            }
        }
        vector<int> res;
        while(!pq.Empty()) {
            res.push_back(pq.Top().second);
            pq.Pop();
        }
        return res;
    }
};

提交后AC!

本节完

本文分享自微信公众号 - 光城(guangcity),作者:lightcity

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 机器学习之数据之美

    昨天看了一下机器学习的东西,发现在做特征工程时,需要用到seaborn的可视化方法。

    公众号guangcity
  • Hive SQL开窗函数实战

    开窗函数是数据的一种查询统计语法糖,多是用于离线统计,这同时也是大数据技术栈的应用场景。今天学习Hive SQL的开窗(窗口)函数,对比与MySQL,在MySQ...

    公众号guangcity
  • 回归Android,继续刷题

    这两天要做个安卓项目,哎,我之前是做安卓开发的,做了半年多,后面就没做了,距离现在至少1年半有余。

    公众号guangcity
  • 小顶堆Java实现

    参考文章: 漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析 http://blog.csdn.net/touch_2011/article/detai...

    囚兔
  • R语言实战:心血管病分析实例

    AI之禅
  • R建立一个临床预测分类

    AI之禅
  • Python与Tableau相结合,万字长文搞定传统线下连锁店数据分析

    这是kaggle上的一份巴西传统线下汽车服务类连锁店的实际销售数据,大小约3.43G,包含了从2017年3月31日到2020年4月1日大约2600万多的销售数据...

    朱小五
  • 使用GAN生成序列数据

    【导读】序列数据十分常见,但由于隐私,法规限制了对有用数据的访问,这极大地减慢了对研发至关重要的有用数据的访问。因此产生了对具有高度代表性但又完全私有的合成序...

    公众号机器学习与生成对抗网络
  • 05-树7 堆中的路径 (25分)

    将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i,打印从H[i]到根结点的路径。

    AI那点小事
  • Python算法题----列表去重

    有这样一个列表[1, 1, 1, 2, 3, 3, 2, 4, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 10, 10], 写一个...

    py3study

扫码关注云+社区

领取腾讯云代金券