算法全讲4】比较器和堆"/>
【左程云算法全讲4】比较器和堆
系列综述:
💞目的:本系列是个人整理为了秋招面试
的,整理期间苛求每个知识点,平衡理解简易度与深入程度。
🥰来源:材料主要源于左程云算法课程进行的,每个知识点的修正和深入主要参考各平台大佬的文章,其中也可能含有少量的个人实验自证。
🤭结语:如果有帮到你的地方,就点个赞和关注一下呗,谢谢🎈🎄🌷!!!
🌈【C++】秋招&实习面经汇总篇
文章目录
- 堆
- 比较器
- 参考博客
😊点此到文末惊喜↩︎
堆
- 完全二叉树的数组表示,当前结点下标为i(第0位不用,从而可以使用移位操作进行快速处理)
- 左孩子: 2 ∗ i ⟺ ( i < < 1 ) 2 * i \iff (i << 1) 2∗i⟺(i<<1)
- 右孩子: 2 ∗ i + 1 ⟺ ( i < < 1 ∣ 1 ) 2 * i + 1 \iff (i << 1 | 1) 2∗i+1⟺(i<<1∣1)
- 父结点: ( i ) / 2 ⟺ ( i > > 1 ) (i) / 2 \iff (i >> 1) (i)/2⟺(i>>1)
- 堆
- 通过下沉和上浮操作,进行处理
// 插入底部,插入结点自底向上上浮
void HeapUp(vector<int> &vec, int index) {// 若当前结点大于父亲结点,则交换while (vec[index] > vec[(index - 1) / 2]) {swap(vec[index], vec[(index - 1) / 2]);index = (index-1) / 2;}
}// 弹出根节点,插入结点自顶向下下沉
void HeapDown(vector<int> &vec, int index, int heap_size) {int left = index * 2 + 1;while (left < heap_size) { // 表示孩子,即至少有一个左孩子// 有右孩子 && 右孩子值大于左孩子 则最大下标为右孩子,否则是左孩子int largest = left + 1 < heap_size && vec[left+1] > vec[left] ? left+1 : left;// largest中存储自己和左右孩子中最大的largest = vec[largest] > vec[index] ? largest : index;if (largest == index) break; // 如果是根结点则停止swap(vec[largest], vec[index]);// 迭代条件index = largest;left = index * 2 + 1;}
}
// 堆排序
void HeapSort(vector<int> vec) {if (vec.empty() || vec.size() < 2) return ;// 依次将每个数插入,建立大根堆for (int i = 0; i < vec.size(); ++i) {HeapUp(vec, i);}// 每次将大根堆的堆顶元素与数组尾元素交换int heap_size = vec.size();swap(vec[0], vec[--heap_size]);while (heap_size > 0) {HeapDown(vec[0], vec[head_size]);swap(vec[0], vec[--heap_size]);}
}
- 已知一个几乎有序的数组, 若把数组排好序,每个元素移动的距离一定不超过k,并且k相对与数组长度比较小
- 将前k个数放入小根堆中,每次弹出一个堆顶元素,并将下一个数加入堆中
在这里插入代码片
比较器
- 比较器
- 原理:通过重载比较运算符,然后进行两个元素的按某种条件的大小比较
- 优点:可用于泛型编程
- 自定义cmp函数,传入堆中,从而实现自定义的比较
🚩点此跳转到首行↩︎
参考博客
- 对数器
- 单调队列
- 快速链表quicklist
- 《深入理解计算机系统》
- 侯捷C++全系列视频
- 待定引用
- 待定引用
- 待定引用
更多推荐
【左程云算法全讲4】比较器和堆
发布评论