最新域名网站查询,简要描述网站开发过程,wordpress商场插件,网站 数据报表如何做你了解我#xff0c;最干净的轮廓#xff0c; 握住小小风车和放肆的梦~ 堆是一个不错的数据结构#xff0c;而在计算机中#xff0c;无法表示二叉分支结构#xff0c;因此我们经常会看到使用线性表来作为堆的存储容器。在接触堆的时候#xff0c;我们是把它…
你了解我最干净的轮廓 握住小小风车和放肆的梦~ 堆是一个不错的数据结构而在计算机中无法表示二叉分支结构因此我们经常会看到使用线性表来作为堆的存储容器。在接触堆的时候我们是把它拿来同其他排序算法来看待的但其实我们经常使用的是快排或者归并亦或者性能更加优越的选择快排。堆的应用场景实质上转移到了查找问题例如TopK等。很多语言也提供了以堆为底层的数据结构例如C中的priority_queue,Java中的PriorityQueue……
如何实现一个堆排序 我们对任意一个堆的定义是一个完全二叉树当一个父节点的值大于左右子节点的值则称为大堆反之如果一个父节点的值小于左右节点的值则被称之为小堆。 建堆的方法有两种一种是向上调整法一种是向下调整法。前者的思想是着眼于整个数组后者的思想着眼于分治先将最小的子树进行一次堆排序再不停向上迭代。因为向下调整法实现起来更为简单并且效率更高所以我们选择后者。
(1) 构建一个堆(大堆)
// 找到最后的父节点
for (int i (n - 1 - 1 ) / 2;i 0;--i)
{adjustDown(nums, i);
}void adjustDown(vectorint nums,int parent)
{// 控制下标int n nums.size();int child parent * 2 1;while (child n){// 把更大的换上去if (child1 n nums[child] nums[child 1]) child;// 比较if (nums[parent] nums[child]) {swap(nums[parent], nums[child]);// 更新parent child;child parent * 2 1;}else {// 结束break;}}
} (2) 堆排序 要实现升序排序构建大堆反之构建小堆(因为本篇不是着眼于堆排序不解释)。
void adjustDown(vectorint nums,int parent,int end)
{// 控制下标int child parent * 2 1;while (child end){// 把更大的换上去if (child1 end nums[child] nums[child 1]) child;// 比较if (nums[parent] nums[child]) {swap(nums[parent], nums[child]);// 更新parent child;child parent * 2 1;}else {// 结束break;}}
}void HeapSort(vectorint nums)
{// 建堆int n nums.size();// 找到最后的父节点for (int i (n - 1 - 1 ) / 2;i 0;--i){adjustDown(nums, i,n);}// 排序int end n - 1;while (end 0){// 因为构建的是大堆所有后面的数一定是小数swap(nums[end], nums[0]); // 同堆顶交换 让最大的数 在最后一个adjustDown(nums, 0,end);// 排序好一个数end--;}for (auto n : nums)cout n ;cout endl;
} ——前言 1、最后一块石头的重量
(1) 题目解析 (2) 算法原理
C:
class Solution {
public:int lastStoneWeight(vectorint stones) {// 寻找大数构建大堆priority_queueint,vectorint,lessint heap;// 入队列for(auto n:stones) heap.push(n);// 模拟出队列while(heap.size() 1){int x heap.top();heap.pop();int y heap.top();heap.pop();// 插入差值heap.push(x-y);}return heap.size() 0 ? 0:heap.top();}
};
Java:
class Solution {public int lastStoneWeight(int[] stones) {PriorityQueueInteger heap new PriorityQueue((a, b) - b - a);for(int n:stones) heap.offer(n);// 模拟while(heap.size() 1){int a heap.poll();int b heap.poll();heap.offer(a-b);}return heap.isEmpty() ? 0 : heap.peek();}
} 2、数据流中的第K大元素
(1) 题目解析 这也是一个经典的topK问题对于要找第K大的数我们需要构建是小堆而不是大堆。反之要查找第K小的数我们需要构建的是大堆而不是小堆。 (2) 算法原理 c:
class KthLargest {
public:// 构建小堆priority_queueint,vectorint,greaterint _heap;int _k; // 构建多大的kKthLargest(int k, vectorint nums) {_k k;// 入队列for(auto n:nums){_heap.push(n);if(_heap.size() _k) _heap.pop(); // 剔除多余数}}int add(int val) {_heap.push(val);if(_heap.size() _k) _heap.pop();return _heap.top();}
}; java:
class KthLargest {PriorityQueueInteger heap;int _k;public KthLargest(int k, int[] nums) {_k k;heap new PriorityQueue(); // 默认是小堆for(int x:nums){heap.offer(x);if(heap.size() _k) heap.poll();}}public int add(int val) {heap.offer(val);if(heap.size() _k) heap.poll();return heap.peek();}
} 3、前K个高频单词
(1) 题目解
(2) 算法原理 class Solution {
public:typedef pairint,string PSI; // 频次与字符串 用于比较struct cmp{templateclass Tbool operator()(T t1,T t2){return (t1.first t2.first) || (t1.first t2.first) (t1.second t2.second);}};vectorstring topKFrequent(vectorstring words, int k) {unordered_mapstring,int hash; // 统计频次for(auto str:words) hash[str];// 普通的比较函数: less\greater 不能满足我们的要求// 所以我们得更换比较函数: 这里我们采用的是 仿函数priority_queuePSI,vectorPSI,cmp heap;for(auto n:hash){heap.push({n.second,n.first});if(heap.size() k) heap.pop();}// 倒序vectorstring ret(k);for(int ik-1;i0;--i){ret[i] heap.top().second;heap.pop();}return ret;}
}; 4、数据流中的中位数
(1) 题目解析 前两者解法都是很好想的前提就是保证数组有序再来找中位数。但我们这里选择的解法不是其中的任意一种。
(2) 算法原理
class MedianFinder {
public:priority_queueint,vectorint,lessint _left;priority_queueint,vectorint,greaterint _right;MedianFinder() {}void addNum(int num) {if(_left.size() _right.size()){if(_left.empty() || num _left.top()){// 直接进入_left.push(num);}else{// 替换_right.push(num);_left.push(_right.top());_right.pop();}}else{if(num _left.top()){_left.push(num);_right.push(_left.top());_left.pop();}else{_right.push(num);}}}double findMedian() {if(_left.size() _right.size()) return (_left.top() _right.top()) / 2.0;return _left.top(); // mn1}
}; 本篇到此结束感谢你的阅读。
祝你好运向阳而生~
