-
数组实现的大根堆
2019-06-18 10:21:32大根堆 根节点是所有节点中数值最大的节点 父节点的值总比子节点大 基本操作 Insert 向堆中插入一个值 Update 更新 Heapify 堆化 RemoveTop 删除堆顶元素 GetTop 获得堆顶元素 辅助操作 获得父节点 获得左孩子 ...堆
- 一种树状的数据结构
大根堆
- 根节点是所有节点中数值最大的节点
- 父节点的值总比子节点大
- 基本操作
- Insert 向堆中插入一个值
- Update 更新
- Heapify 堆化
- RemoveTop 删除堆顶元素
- GetTop 获得堆顶元素
- 辅助操作
- 获得父节点
- 获得左孩子
- 获得右孩子
- 获得当前容量
- 判断一个节点是否是叶子节点
- 交换2个节点的位置
数组大根堆
- 用数组实现的大根堆
- 作用
- 堆排序
- 求最大值
- 求第n大的值
- 基本操作
- Insert 向堆中插入一个值
- Update 从指定的节点开始把较大的值和父节点交换直到处理到根节点
- Heapify 从指定的节点开始把较小的节点和子节点中较大的那个交换直到处理到叶子节点
- RemoveTop 删除堆顶元素
- 把堆尾部的元素换到堆顶,堆大小-1
- 从堆顶开始执行堆化
- GetTop 获得堆顶元素
- 辅助操作
- 获得父节点
- 父节点和子节点的关系
- leftChildIndex = parentIndex * 2 + 1
- rightChildIndex = parentIndex * 2 + 2
- parentIndex = (childIndex - 1) / 2
- 父节点和子节点的关系
- 获得左孩子
- 获得右孩子
- 获得当前容量
- 判断一个节点是否是叶子节点
- 如果一个节点的孩子index超过当前容量说明这个节点没有子节点,故为叶子节点
- 交换2个节点的位置
- 获得最大容量
- 根据index判断一个节点是否在堆中
- 获得父节点
- 实现代码
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace DataStructure { public class ArrayMaxHeap { int[] array; int size; int maxSize; public void Build(int maxSize) { array = new int[maxSize]; this.maxSize = maxSize; size = 0; } public int GetSize() { return size; } public int GetMaxSize() { return maxSize; } //尾部追加再更新 public void Insert(int value) { if (size == maxSize) { throw new Exception("size must <= max size"); } array[size] = value; size++; Update(size - 1); } //把大的值往堆顶放 //把一个大的值从下面换到父节点,直到堆顶 void Update(int index) { if (index == 0) return; if (index < 0) throw new ArgumentException("index must >= 0"); if (array[index] > array[ParentIndex(index)]) { Swape(index, ParentIndex(index)); Update(ParentIndex(index)); } } public int LeftChildIndex(int index) { return index * 2 + 1; } public int RightChildIndex(int index) { return index * 2 + 2; } public int ParentIndex(int index) { return (index - 1) / 2; } public bool IsLeaf(int index) { return !IsInHeap(LeftChildIndex(index)); } public bool IsInHeap(int index) { return 0 <= index && index < size; } private void Swape(int index1, int index2) { var temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } public int GetTop() { return array[0]; } void Heapify(int index) { if (IsLeaf(index)) { return; } //找到左边和右边最大的那个子节点,如果子节点更大,交换,对子节点执行堆化,把小的值往堆底放 //左子节点更大 if (array[LeftChildIndex(index)] > array[RightChildIndex(index)]) { if (array[index] < array[LeftChildIndex(index)]) { Swape(index, LeftChildIndex(index)); Heapify(LeftChildIndex(index)); } } //右孩子更大,比较右孩子 else if (array[index] < array[RightChildIndex(index)]) { Swape(index, RightChildIndex(index)); Heapify(RightChildIndex(index)); } } //取出堆顶,把尾部放到堆顶,执行堆化 public int RemoveTop() { if (size == 0) throw new Exception("no element in heap"); var top = array[0]; array[0] = array[size - 1]; size--; Heapify(0); return top; } public static void Test() { var array = new int[] { 2, 4, 6, 7, 8, 3, 2, 5 }; var solution = new ArrayMaxHeap(); solution.Build(array.Length); foreach (var num in array) { solution.Insert(num); BaseSolution.print(solution.GetTop()); BaseSolution.print(','); } BaseSolution.println(); while (solution.GetSize() > 0) { BaseSolution.print(solution.RemoveTop()); BaseSolution.print(','); } } } }
-
大根堆和堆排序的原理与实现
2020-12-01 01:04:47因为插入一个元素时,列表已经是一个大根堆,所以当出现父元素大于自己时,就没有必要继续,因为父元素的父元素值更大。 shift down 删除一个元素时,把该元素和列表的最后一个元素交换。然后列表的长度减一(如果...shift up
- 插入一个元素时,把元素追加到列表的最后,也就是堆的叶子节点上。然后执行shifup操作,对新元素进行从下往上的调整。
- 判断当前元素是否比父节点更大,如果是,则交换。否则就终止。
- 因为插入一个元素时,列表已经是一个大根堆,所以当出现父元素大于自己时,就没有必要继续,因为父元素的父元素值更大。
shift down
-
删除一个元素时,把该元素和列表的最后一个元素交换。然后列表的长度减一(如果用
count
计数的话)。剩余的元素进行shiftdown操作。 -
shiftdown,如果两个孩子中存在比自己更大的元素,就和那个孩子交换值。然后这个孩子作为根,继续这个操作。
-
如下: 插入时执行shiftUp,删除时执行shiftDown
// 堆排序 class Heap{ private List<Integer> data; public Heap(){ this.data = new ArrayList<>(); } public void insert(int value){ this.data.add(value); this.shiftUp(this.data.size() - 1); } public int pop(){ this.swap(0, this.data.size() - 1); int res = this.data.remove(this.data.size() - 1); this.shiftDown(0); return res; } /** * 上移,元素加入时执行 * @param k */ public void shiftUp(int k){ // 0 元素没有父元素 // 当出现k比父元素小的时候,就没有必要继续下去,因为,父元素的父元素一定是更大的数 while(k >= 1 && data.get(k) > data.get((k - 1) / 2)){ swap(k, (k - 1) / 2); k = (k - 1) / 2; } } /** * 下移,调整堆时执行 * @param k */ public void shiftDown(int k){ // 省略了对左孩子的判断 while(2 * k + 1 < data.size()){ int child = 2 * k + 1; if(child + 1 < this.data.size() && this.data.get(child) < this.data.get(child + 1)){ child += 1; } if(this.data.get(child) > this.data.get(k)){ this.swap(k, child); } k = child; } } public void swap(int left, int right){ int temp = this.data.get(left); this.data.set(left, this.data.get(right)); this.data.set(right, temp); } } // main _215_数组中的第k个最大元素.Heap2 heap = handle.new Heap2(); // 建立堆 for(int item : list){ heap.insert(item); } for(int item : list){ System.out.print(heap.pop() + " "); }
heapify
- 不需要一个一个的插入元素,可以直接对原数组的所有非叶节点进行heapify,即可构成一个大根堆。
((size - 1) - 1) / 2
表示最大下标减一。当然,用size/2
也行,多出的几个元素都是叶子节点,都可以当成是只有一个元素的堆。
public Heap2(List<Integer> list){ this.data = new ArrayList<>(list); heapify(); } public void heapify(){ for(int i = (data.size() - 1 - 1) / 2; i >= 0; --i){ shiftDown(i); } }
就地排序
- 这里的nums数组的数据从0开始拍,这样的话,按照如下方式计算父子节点
- 左孩子:
index * 2 + 1
- 右孩子:
index * 2 + 2
- 父节点:
(index - 1) / 2
或者(length -1 -1)/2
。有的算法直接用(length / 2)
也不会有错,因为最右边的叶子节点都可以看成是单个的大根堆。
- 左孩子:
class Heap { public void heapSort(int [] nums){ // 从第一个非叶节点开始,执行shiftdown操作 int size = nums.length; // 建立一个堆 // 很多携程(size-1)/2 或者 size/2都行 for( int i = (size -1 - 1)/2; i >= 0; --i){ shiftDown(nums, i, size); } // 从堆中取元素 for (int i = size - 1; i > 0; i --){ swap(nums, 0, i); // i 元素被放到0位置 shiftDown(nums, 0, i); // 重新堆0位置的元素shiftdown } } /** * 对第i个元素执行下移操作。大根堆 * @param nums * @param i */ public void shiftDown(int [] nums, int k, int size){ // 用while 少了一次循环,避免了递归 while( 2 * k + 1 < size){ int child = 2 * k + 1; // 左孩子 if ( child + 1 < size && nums[child+1] > nums[child]) child += 1; // 右孩子 if (nums[k] < nums[child]){ swap(nums, child, k); } k = child; // 从被交换的孩子开始,继续往下迭代。直到到达叶子节点 } } public void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }
-
大根堆创建于排序
2019-05-23 17:18:21创建大根堆 static void buildBigHeap(int[] array, int last) { //从最大的非叶子节点开始(last - 1 /2),到根节点终止 for (int i = (last -1) / 2; i >= 0; i--) { int k = i; //判断是否超过数组...创建大根堆
static void buildBigHeap(int[] array, int last) { //从最大的非叶子节点开始(last - 1 /2),到根节点终止 for (int i = (last -1) / 2; i >= 0; i--) { int k = i; //判断是否超过数组界限,第一轮比较完,该子节点作为父节点时是否为最大值情况 while ((2 * k) + 1 <= last){ //记录最大值的下标 int bigIndex = 2*k+1; //判断是否右子节点,如果相等无右子节点。小于则右 if(bigIndex < last){ //判断左右子节点的大小 if(array[bigIndex] < array[bigIndex + 1]){ bigIndex++; } } //最大子节点和父节点比较 if(array[k] < array[bigIndex]){ MyUtil.swap(array,k,bigIndex); System.out.println(Arrays.toString(array)+"有交换"+ "\t" +"父节点 = " + k + "\t" + "最大子节点 = " + bigIndex); k = bigIndex; } else { System.out.println(Arrays.toString(array)+"无交换"); break; } } } }
创建大根堆思路
首先找到最后的父节点 ,从下标0开始所以为int last = (array.length -1 -1 )/2
所以父节点一共有0 到 last 个
记录一下当前父节点的下标
以左子节点来判断是否超过数组界限
找出左右子节点的最大值
然后和父节点的值进行比较 交换位置大根堆排序code
public static void headSort(int[] nums){ System.out.println("原始数组 =" + Arrays.toString(nums)); System.out.println("-----------------------------------"); for(int i = nums.length - 1 ; i > 0; i--){ buildBigHeap(nums, i); MyUtil.swap(nums, i , 0); } }
思路
每次都将前面的值放到最后
因为每次放完后在进行大根堆重组的时候,重组数组大小减1,所以 9 8 7 6 5 4 3 2 1 的顺序排成从小到大测试code
public static void main(String[] args){ int[] array = MyUtil.createArray(); int[] arrays = new int[array.length]; System.arraycopy(array,0,arrays,0,array.length); //系统排序 Arrays.sort(arrays); //堆排序 HeapSort.headSort(array); boolean compare = MyUtil.compare(array,arrays); System.out.println(compare); }
-
day36: 数据流中的中位数(大根堆小根堆)
2020-07-01 11:06:42问题描述: 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于...首先向大根堆里面加入元素,如果加入元素不满足条件,那么再进行下一步操作,其中条件是:1)大根堆问题描述:
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
样例- 输入:1, 2, 3, 4
- 输出:1,1.5,2,2.5
解释:每当数据流读入一个数据,就进行一次判断并输出当前的中位数。
使用大根堆维护序列的前半部分,使用小根堆维护序列的后半部分。序列是指的从小到大排列。首先向大根堆里面加入元素,如果加入元素不满足条件,那么再进行下一步操作,其中条件是:1)大根堆里面的元素最多只能比小根堆的元素多1个,如果多两个的话,就需要将大根堆的元素弹出来放到小根堆里面去,2)如果大根堆里面的堆顶元素大于小根堆里面的堆顶元素,那么这样的序列不是有序的,则需要交换这两个元素使得大的部分在小根堆里,小的部分在大根堆里。
class Solution { public: priority_queue<int> max_heap; priority_queue<int,vector<int>,greater<int>> min_heap; void insert(int num){ max_heap.push(num); if(min_heap.size()&&max_heap.top()>min_heap.top()) { auto maxv=max_heap.top(),minv=min_heap.top(); max_heap.pop(),min_heap.pop(); max_heap.push(minv),min_heap.push(maxv); } if(max_heap.size()>min_heap.size()+1) { min_heap.push(max_heap.top()); max_heap.pop(); } } double getMedian(){ if(max_heap.size() + min_heap.size() & 1) return max_heap.top(); return (max_heap.top()+min_heap.top())/2.0; } };
-
栈、队列、小根堆和大根堆的Java API使用
2019-05-15 21:43:44下面对Java中的栈、队列、小根堆和大根堆做一个简单的介绍。 它们都有共用的collections接口中定义的常见函数isEmpty(),可以判断该数据结构中是否还有元素。 栈 Java中有Stack类,但现在已经过时了,不推荐使用。一... -
【剑指】73,数据流的中位数(大根堆和小根堆)
2020-03-21 00:53:07**题目描述** 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间...利用两个堆,一个大根堆一个小根堆。然后插入的时候通过两者的size和顶部的数字进行判断。... -
PAT_甲级_1155 Heap Paths (30point(s)) (C++)【DFS/大根堆、小根堆判断】
2020-04-03 14:25:258 25 70 8 25 82 8 38 52 8 38 58 60 Min Heap Sample Input 3: 8 10 28 15 12 34 9 8 56 Sample Output 3: 10 15 8 10 15 9 10 28 34 10 28 12 56 Not Heap 题目大意 判断一棵完全二叉树为大根堆、小根堆,或者不是... -
关于满二叉树、完全二叉树以及完全二叉树的大根堆小根堆
2020-03-20 21:28:23满二叉树 完全二叉树的定义 满二叉树就是每一层节点个数都是满的二叉树。第n层节点个数 = pow(2,n - 1...关于完全二叉树的几个面试题目一:判断是不是完全二叉树 思路:层次遍历:当前节点左子树不空放入queu... -
用自底向上算法为一组整数构造一个大根堆。_分享一些数据结构与算法常用的算法技巧总结...
2020-11-18 18:10:16一、巧用数组下标数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些字母作为下标,在遍历的... -
用自底向上算法为一组整数构造一个大根堆。_一些常用的算法技巧总结---不看吃亏系列...
2020-12-03 23:54:501. 巧用取余有时候我们在遍历数组的时候,会进行越界判断,如果下标差不多要越界了,我们就把它置为0重新遍历。特别是在一些环形的数组中,例如用数组实现的队列。往往会写出这样的代码:for (int i = 0; i < N; ... -
堆的判断
2018-04-26 17:58:37= k[2*i+1]大根堆:k[i] >= k[2*i] 且 k[i] >= k[2*i+1]#include<iostream>(小根堆判断)using namespace std;int main(){ int n; cin>>n; int a[n]; f... -
关于一个堆的类型判断
2017-04-14 13:49:563(3,3) 由广义表构成的二叉树,是属于大根堆还是小根堆呢? 求大侠解答一下,我是小白 -
如何判断一个序列是否为堆?
2015-09-17 03:27:42下列各序列中不是堆的是() ...参考答案是C,说A和D都是大根堆,但觉得答案有问题,按照“大根堆大于等于左右子节点的值”,A中的36小于47,大于30;同样地,D中的12小于24和36,这有问题吧?求大侠指教,谢谢 -
堆的实现 (L2-012 关于堆的判断 (25 分))
2019-01-28 17:38:48堆分成大顶堆和小顶堆,大根堆要求根节点的关键字既大于或等于左子树的关键字值,又大于或等于右子树的关键字值。小顶堆相反。 —————————————————————————————— 一堆的建立(以小... -
PAT 1155 Heap Paths (30 分)
2019-01-21 13:49:01题目传送门 这题.....看个标题和数据基本就能...判断大根堆和小跟堆我是判断了两次,先判断是否是大根堆,在判断是否是小跟堆,判断方法就是遍历每个点,判断每个点是不是都满足堆得性质 #include<iostrea... -
堆排序
2020-08-09 22:33:53建立大根堆的时间复杂度是log(N),与大根堆的高度有关。 小根堆: 任何一棵子树的最小值都是头部 数组如何建立大根堆: 从0开始遍历数组,0-i位置之间形成大根堆。判断i位置和(i-1)/2,即父节点的大小,假如比父节点... -
c语言判断二叉树是不是二叉排序树_堆排序就这么简单
2021-01-18 18:56:21堆分为大根堆和小根堆,是完全二叉树。前面我已经有二叉树入门的文章了,当时讲解的是二叉查找树,那上面所说的完全二叉树是怎么样的一种二叉树呢??还有满二叉树又是怎么的一种二叉树呢??甚至还有完满二叉树??... -
天梯题集——关于堆的判断(小顶堆模板题、模拟构造过程)
2020-11-25 17:16:46如果根节点最小,称之为小顶堆(或小根堆),如果根节点最大,称之为大顶堆(或大根堆)。 注意:堆的左右孩子没有大小的顺序。 关于堆的判断 这道题目完全可以看成一道堆的模板题,只要构建出小顶堆其他都好说。... -
二叉堆
2020-02-06 22:02:45也就是我们通常说的大根堆和小根堆。而这里的最大和最小是根据题目中的优先级来判断最大最小的,而不是我们所想的大和小。 左图为最大堆,右图为最小堆(他们优先级为数字大小)。同时他没棵子树也是一个最小(大)... -
LuoguP1168 中位数 堆(STL)题解
2019-09-26 02:35:45首先,维护一个大根堆和一个小根堆 大根堆维护数列中小的部分,小根堆维护数列中大的部分 然后,每次输入两个数,大的加入小根堆,小的加入大根堆 为什么? 我不知道 还有一个玄学操作: 把两个堆堆顶判断一下,大根... -
二叉堆--优先队列
2019-02-27 21:26:17堆:堆常见的二叉堆,这种数据结构有大根堆和小根堆。对于大根堆来说,每个父节点是大于他的两个孩子节点的。也就是最大值在根节点。小根堆与之相反。如果堆用数组实现的话,如果从0开始计数,那么一个孩子的父节点... -
二叉堆的插入与删除
2020-02-06 21:23:273.堆一般有俩种形式,大根堆和小根堆,大根堆是堆顶的优先级最大,小根堆就是堆顶的优先级最小 二.堆的操作 一. 插入 堆的插入就是把新的元素放到堆底,然后去判断是否符合这个位置的要求,如果符合就丢在那里了,... -
洛谷 P3466 [POI2008]KLO-Building blocks 支持删除的堆
2019-08-01 14:32:48思路上面几位都说得比较清晰了,就是动态维护中位数,然后每次求最小代价,当时我脑袋一热,就想到了对顶堆,就是定义1个小根堆和1个大根堆,每次判断当前的数如果小于大根堆顶,就加入大根堆,否则加入小根... -
堆和优先队列总结
2020-04-30 16:56:35满足任意结点的值都大于其子树中结点的值,叫做大堆,或者大根堆,或者最大堆 反之则是小堆,或者小根堆,或者最小堆 向下调整 前提:左右子树必须是一个堆才能调整 过程(以小堆为例) 1.index如果已经是叶子节点,...
收藏数
121
精华内容
48
-
Mycat 实现 MySQL的分库分表、读写分离、主从切换
-
一天学完MySQL数据库
-
【背包问题】基于matlab离散粒子群算法求解01背包问题【含Matlab源码 423期】
-
朱老师C++课程第3部分-3.6智能指针与STL查漏补缺
-
PPT大神之路高清教程
-
linux基础入门和项目实战部署系列课程
-
JMETER 性能测试基础课程
-
spider数据挖掘-----20、关于破解字符的验证码
-
【爱码农】C#制作MDI文本编辑器
-
MySQL 高可用(DRBD + heartbeat)
-
java 序列化对象 内存_java反序列化引起的内存溢出怎么解决
-
前端----Boostrap(二)
-
java中io流桥接器_io流
-
MySQL Router 实现高可用、负载均衡、读写分离
-
ELF视频教程
-
java 序列化 protobuf_Java序列化和Protobuf
-
java 序列化 引用_java 序列化之当序列化遭遇继承,组合,对象引用
-
MySQL 性能优化(思路拓展及实操)
-
airmon-ng破解wifi
-
libFuzzer视频教程