-
2021-03-10 14:55:26
1、PriorityQueue默认情况下建立的是最小堆,堆顶元素是最小值。如果输出这个堆,得到的序列是递增的。
2、可以自定义比较器,使得PriorityQueue建立最大堆,堆顶元素是最大值,如果输出这个堆,得到的序列是递减的。
首先看一下PriorityQueue在默认的情况下是如何使用的:
import java.util.PriorityQueue; public class Test9 { public static void main(String[] args) { int[] a = {2,4,8,6,5,1,3,7}; PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //默认构造函数,建立最小堆 for(int i=0;i<a.length;i++) { minHeap.offer(a[i]); } while(!minHeap.isEmpty()) { System.out.print(minHeap.poll()+" "); } System.out.println(); //输出(升序):1 2 3 4 5 6 7 8 } }
然后看一下如何使用比较器建立最大堆:
mport java.util.PriorityQueue; import java.util.Comparator; public class Main1 { public static void main(String[] args) { int[] a = {2,4,8,6,5,1,3,7}; //使用Comparator,重写其中的compare函数 PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() { public int compare(Integer o1, Integer o2) { //若写成return o1.compareTo(o2) 或者 return o1-o2表示升序 //return o2-o1; //表示降序 return o2.compareTo(o1); //表示降序 } }); for(int i=0;i<a.length;i++) { maxHeap.offer(a[i]); } while(!maxHeap.isEmpty()) { System.out.print(maxHeap.poll()+" "); } System.out.println(); //输出(升序):8 7 6 5 4 3 2 1 } }
此外还可以用另外一种更加简便的方式建立最大堆,利用Collections容器中的reverseOrder()函数:
import java.util.PriorityQueue; import java.util.Collections; import java.util.Comparator; public class Main1 { public static void main(String[] args) { int[] a = {2,4,8,6,5,1,3,7}; //利用Collections.reverseOrder()函数,将序列反转,即将升序反转为倒叙,从而建立最大堆 PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder()); for(int i=0;i<a.length;i++) { maxHeap.offer(a[i]); } while(!maxHeap.isEmpty()) { System.out.print(maxHeap.poll()+" "); } System.out.println(); //输出(升序):8 7 6 5 4 3 2 1 } }
在一些算法题中,经常需要找出一个数组中最小(大)的K个数,这类题都是用排序算法把数组排序,然后把符合要求的K个数输出就可以了。如果我们用堆排序算法来做的话,就需要手写堆排序的算法,但是有了PriorityQueue,我们就不需要自己实现那么长的代码,直接调用PriorityQueue就可以了。下面看一下如何用PriorityQueue找出数组中最小的K个数。
import java.util.PriorityQueue; import java.util.Collections; public class Main2 { public static void main(String[] args ) { int[] a = {1,2,7,6,5,4,3}; GetLeastNumbers_Solution(a,5); //找出数组中最小的5个数 } public static void GetLeastNumbers_Solution(int[] input, int k) { PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder()); for (int i = 0; i < input.length; i++) { if (maxHeap.size() < k) { maxHeap.add(input[i]); } else { //由于是最大堆,所以堆顶元素是最大的,所以每次比较堆顶元素就可以了,只要小于堆顶元素就加入堆中。 if (input[i] < maxHeap.peek()) { maxHeap.remove(); //如果小于堆顶元素,则将堆顶元素去掉 maxHeap.add(input[i]); //将数字插入当前堆中,PriorityQueue会自动重新建堆 } } } while(!maxHeap.isEmpty()) { System.out.print(maxHeap.poll()+" "); } System.out.println(); } } // 输出: 5 4 3 2 1
更多相关内容 -
数据结构学习笔记(三) 树形结构之筛选法建立最小堆
2018-01-28 19:16:18以下是使用筛选法建立最小堆的代码,用于建堆的数据为{35,26,48,10,59,64,17,23,45,31}。 筛选法也即,从堆的最右下一个分支节点起,自下而上遍历每一个分支节点,使得以该分支节点为根的子树成为最小堆。 //筛选...以下是使用筛选法建立最小堆的代码,用于建堆的数据为{35,26,48,10,59,64,17,23,45,31}。
筛选法也即,从堆的最右下一个分支节点起,自下而上遍历每一个分支节点,使得以该分支节点为根的子树成为最小堆。//筛选法+建立最小堆 #include<iostream> using namespace std; //类型定义与变量说明 const int DefaultSize=100; typedef int datatype; typedef struct { datatype key;//关键字 //......其他属性字段 }node; typedef struct { node *Heap; int CurrentSize; int MaxHeapSize; }minHeap; minHeap mh; int start,EndOfHeap; //筛选法 void FilterDown(minHeap &mh,int start,int EndOfHeap) { int i=start,j=2*i+1; node temp=mh.Heap[i]; while(j<=EndOfHeap) { if(j<EndOfHeap&&mh.Heap[j].key>mh.Heap[j+1].key) j++; if(temp.key<=mh.Heap[j].key) break; else { mh.Heap[i]=mh.Heap[j]; i=j; j=2*j+1; } mh.Heap[i]=temp; } } //建立最小堆 void MinHeap(minHeap &mh,node A[],int n) { int i,CurrentPos; mh.MaxHeapSize=DefaultSize<n?n:DefaultSize; mh.Heap=new node[mh.MaxHeapSize]; if(mh.Heap==NULL) { cout<<"Memory Allocation Error1"<<endl; return; } for(i=0;i<n;i++) mh.Heap[i]=A[i]; mh.CurrentSize=n; CurrentPos=(mh.CurrentSize-2)/2; while(CurrentPos>=0) { FilterDown(mh,CurrentPos,mh.CurrentSize-1); CurrentPos--; } } //测试方法 int main() { node A[10]={35,26,48,10,59,64,17,23,45,31}; MinHeap(mh,A,10); for(int i=0;i<10;i++) cout<<mh.Heap[i].key<<" "; cout<<endl; return 0; }
-
matlab建立最小堆算法实现
2019-11-06 09:10:21最小堆的定义 ...利用数组建立最小堆 leaf_name=['A','B','C','D','E','F','G','H']; leaf_data=[10,1,1,11,1,1,8,5]; my_heap=heap(); my_heap.min_heap_create(leaf_name,leaf_data); 函数定义如下: ...最小堆的定义
最小堆是一颗完全二叉树,他的每一个节点的值不大于其左右子节点的值。
利用数组建立最小堆
leaf_name=['A','B','C','D','E','F','G','H']; leaf_data=[10,1,1,11,1,1,8,5]; my_heap=heap(); my_heap.min_heap_create(leaf_name,leaf_data); 函数定义如下: function heap = heap() heap.size=0; heap.name=[]; heap.data=[]; end function min_heap_create(heap,name,data) N=length(name); for n=1:N heap.name(n)=name(n); heap.data(n)=data(n); heap.size=heap.size +1; end end
运行结果如下:
node 1–>A–>10
node 2–>B–>1
node 3–>C–>1
node 4–>D–>11
node 5–>E–>1
node 6–>F–>1
node 7–>G–>8
node 8–>H–>5
图状表示如下:
节点下沉算法
因为最小堆的子树也是最小堆,所以可以从底部开始建立,采用节点下沉算法。如果子节点的值比本身小,将左右子节点中最小的一个和本身交换,相等的情况下左子节点优先交换。逐步下降,直到本身的节点不大于子节点停止。代码如下:
function heap_down_sink(heap,self) lchild =self*2; rchild =self*2+1; if(lchild <= heap.size && rchild <= heap.size) if(heap.data(self) > heap.data(lchild) || heap.data(self) > heap.data(rchild)) if(heap.data(lchild) <= heap.data(rchild))%左右子树相等的情况下,优先往左子树下沉 heap_swap_node(heap,lchild,self); heap_down_sink(heap,lchild); else heap_swap_node(heap,rchild,self); heap_down_sink(heap,rchild); end end elseif(lchild <= heap.size)%仅仅只存在左叶子树 if(heap.data(self) > heap.data(lchild)) heap_swap_node(heap,lchild,self); end end end
利用上面的节点下降算法调整二叉堆,使之满足最小堆的特性。方法是从最后一个节点开始,逐个运行节点下沉算法,就可以实现要求。函数如下:
function min_heap_adjust(heap) n=heap.size; while(n>=1) heap_down_sink(heap,n) n=n-1; end end
运行结果如下:
node 1–>B–>1
node 2–>E–>1
node 3–>C–>1
node 4–>H–>5
node 5–>A–>10
node 6–>F–>1
node 7–>G–>8
node 8–>D–>11
图状表示如下:
往最小堆中插入节点
插入节点不能破坏堆的特性,因此首先将堆的长度增加一个耽误,然后新增最后一个元素。因为只有新添加的节点可能不满足位置要求,因此对该节点执行上浮操作。具体做法是如果他的值小于其父母节点的值,那么交换两者的值,直到不满足条件为止,即可调整好最小堆。代码如下:
function min_heap_insert(heap,name,data) %新增的节点添加的尾部 heap.size=heap.size +1; heap.name(heap.size)=name; heap.data(heap.size)=data; %新增的节点做上浮的动作,达到排序的效果 heap_up_float(heap,heap.size); end function heap_up_float(heap,self) while(self >=2) parent=floor(self/2); if(heap.data(self) < heap.data(parent)) heap_swap_node(heap,parent,self); end self =parent; end end
执行my_heap.min_heap_insert(‘N’,3)后,运行结果如下:
node 1–>B–>1
node 2–>E–>1
node 3–>C–>1
node 4–>N–>3
node 5–>A–>10
node 6–>F–>1
node 7–>G–>8
node 8–>D–>11
node 9–>H–>5
图状表示如下:从最小堆里面弹出最小的节点
取出最小节点仍然不能破坏最小堆的结构,方法是将根节点和最后一个节点交换,那么最后一个节点就最小的节点。然后将堆的长度减小1个单位,此时只有根节点可能不满足最小堆的特性,执行节点下沉算法,就可以满足要求。代码如下:
function min_heap_popup(heap) heap_swap_node(heap,1,heap.size);%交换根节点和尾结点 heap.size =heap.size -1; heap_down_sink(heap,1);%根节点下沉 end
执行my_heap.min_heap_popup()后运算结果如下:
node 1–>E–>1
node 2–>N–>3
node 3–>C–>1
node 4–>H–>5
node 5–>A–>10
node 6–>F–>1
node 7–>G–>8
node 8–>D–>11
图状表示如下
总结:以上就是最小堆的基本操作,欢迎探讨交流。
-
最小堆建立和堆排序
2018-10-03 10:34:17堆树的定义: ... 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。如下图所示,左边为最小堆,右边为最大堆。 数组与堆 无序数组转化成原始的二叉堆: 4 5 3 ...堆树的定义:
(1)堆树是一颗完全二叉树;
(2)堆树中某个节点的值总是不大于或不小于其孩子节点的值;
(3)堆树中每个节点的子树都是堆树。
当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。如下图所示,左边为最小堆,右边为最大堆。
数组与堆
无序数组转化成原始的二叉堆:
4 5 3 2 6 1 构建最小堆:
元素下沉思想:从无序数组的最后往前遍历,堆树从下层到上层依次搭建完成
1 从叶子节点(无序数组的最后一个元素)出发,把当前的parent设置为无序数组中的最后一个数(也就是叶子节点),依次往前遍历,当parent是叶子节点,就不做操作
2 当parent遍历到非叶子节点,此时,它就有左子节点和右子节点或者只有左子节点。需要做的操作:先在左右子节点中找到最小元素所在的索引,然后将左右子节点中的最小元素与parent的节点,进行比较,如果小于,则交换,同时更新parent和child的位置。否则不交换,退出当前循环。
3 “元素下沉”的终止条件就是父节点的元素值不大于其任意左右子节点的元素值,或者当前父节点无子节点(即当前节点为叶子节点)。
def heap_min(heap): for parent in range(len(heap)-1,-1,-1): child = 2*parent+1 while child <len(heap): if child+1<len(heap) and heap[child+1]<heap[child]: child += 1 if heap[parent]<= heap[child]: break heap[parent],heap[child] = heap[child],heap[parent] parent,child = child,2*child+1 return heap print(heap_min([4,5,3,2,6,1]))
输出结果是:构建了最小堆
堆排序:
是指利用堆(最大堆、最小堆)这种数据结构所设计的一种排序算法。堆是一个完全二叉树的结构,并同时满足如下性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
def sift_down(arr, start, end): root = start while True: # 从root开始对最大堆调整 child = 2 * root + 1 if child > end: break # 找出两个child中交大的一个 if child + 1 <= end and arr[child] < arr[child + 1]: child += 1 if arr[root] < arr[child]: # 最大堆小于较大的child, 交换顺序 arr[root], arr[child] = arr[child], arr[root] # 正在调整的节点设置为root root = child else: # 无需调整的时候, 退出 break def heap_sort(arr): # 从最后一个有子节点的孩子还是调整最大堆 first = len(arr) // 2 - 1 for start in range(first, -1, -1): sift_down(arr, start, len(arr) - 1) # 将最大的放到堆的最后一个, 堆-1, 继续调整排序 for end in range(len(arr) -1, 0, -1): arr[0], arr[end] = arr[end], arr[0] sift_down(arr, 0, end - 1) def main(): # [7, 95, 73, 65, 60, 77, 28, 62, 43] # [3, 1, 4, 9, 6, 7, 5, 8, 2, 10] l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10] print (l) heap_sort(l) print (l) if __name__ == "__main__": main()
-
Python - 最小堆实现与应用
2021-12-04 10:00:13最小堆,又称小根堆(小顶堆)是指根节点(亦称为堆顶)的值是堆里所有节点值中的最小者 -
C语言实现最大堆最小堆的建立以及堆排序
2018-10-22 23:54:55堆可以用数组表示,其中a[0]放入一个最小值,哨兵牌 插入操作放在数组最后,然后如果这个点的父节点大于这个插入的值 那么把子节点的值用父节点替代,父节点继续向上比较,移动到合适位置,在赋相应的值 pop... -
C++构建最小堆
2022-03-01 20:50:45将数组按自下向上扫描,向下调整的方法,调整为最小堆 -
C++ 构建最小堆、最大堆
2020-08-10 08:31:18C++ 实现最大堆和最小堆的构造过程 -
C++使用priority_queue 实现最大最小堆
2022-03-06 22:05:06} 打印信息: 上面是使用基本类型实现的最大/最小堆,而比较常用的是自定义类型的最大最小堆,其实现也不复杂,只需重载大于或小于运算符即可。 2.自定义类型实现 #include #include #include void log(const char*... -
priority_queue 建立最小堆
2017-06-15 13:51:09C++优先队列的基本使用方法 #include #include #include using namespace std; struct node { friend bool operator { return n1.priority "为从小打到排列 ... int value -
最小堆的C++代码实现
2021-11-17 19:51:07给定一维int型数组, 请构造一棵最小堆. 总是优先向左子树调整. Input 输入第1行有一个int型正整数m (m<100), 表示有m行输入. 每行输入的第一个数为int型正整数n (8<n<1000), 后面接着输入n个int型整数. ... -
python 中的最大堆和最小堆(heapq库)
2022-04-11 20:09:55python heapq库 最大堆最小堆 -
数据结构堆的时间复杂度(最大堆,最小堆)
2021-03-11 19:38:24但是从代码层面来看,可能会误以为第二种方式的时间复杂度也是O(NlogN),但第二种方式是从下往上建立堆。举个例子,如下所示,假设堆中存在了N个节点(满足堆的性质),采用第一种方式,再创建N个结点,那么插入第一个... -
matlab实现最小堆
2020-04-08 21:10:22最小堆的含义就不多比比了。最小堆可以应用于排序 ,详情可以参考文章堆排序 。 最小堆的基本函数包括:构造堆,调整堆,弹出堆顶元素,添加一个元素。 目录 1.向下调整堆 2.构造堆 3.弹出堆顶元素 4.添加... -
最小堆排序
2018-06-14 14:57:28堆排序分为最大堆排序和最小堆排序,今天我们...最小堆排序的核心函数是筛选函数,也就是建立最小堆的函数 //最小堆排序 void Swap(ElemType *a, ElemType *b) { assert(a != NULL && b != NULL... -
用数组来建立一个最小堆
2019-05-08 10:34:20#define MaxN 1001 #define MinH -10001 int H[MaxN],size; void Creat() ...//堆都是从下标为1开始的,在0处设置一个哨兵,最小值。 } void Insert(int x) { int i; for(i=++size;H[i/2]>x;i/=2) ... -
堆排序 最大堆 最小堆 Java 实现
2021-02-12 10:18:57建立最小堆需要额外空间?不深究了,归并排序需要额外空间。堆是完全二叉树,所以可以用数组表示。普通的二叉树需要用链表表示。完全二叉树不等于满二叉树。下图是一个完全二叉树。 我们数组下标从0开始。我们可以... -
C++实现最小堆(小顶堆)及堆排序(最小堆实现降序排序)
2020-07-29 14:19:51最小堆(小顶堆)是一种二叉树,树中每个节点都小于他的所有子节点,在最小堆的构建和维护过程中最重要的是**上浮(swim)和下沉(sink)**操作。 MinHeap.h #include <algorithm> /* 最小堆类*/ template<... -
最小堆怎么建立
2015-09-17 17:47:50解决方式是,用一个100个容量的最小堆, 这100个数总数目前已知的最大的100个,而且 堆顶是小的, 在继续遍历时候,只和堆定比较, 如果这个数,比堆顶的大, 就把这个数加入 这个堆。 当遍历完成后,这个最小堆... -
堆排序(最小堆)C++
2018-10-01 15:58:36堆分为大根堆(最大堆)和小根堆(最小堆),堆排序就是二叉堆的升级版,实际上是一棵完全二叉树 不同的是这棵二叉树里每个节点保证父节点都小于孩子节点 最后进行堆排序,将堆顶最小的节点(第一个)与最后一个... -
最小堆的建立及堆排序
2020-02-02 17:51:29堆在很多方面都有运用,这里写一下将一个完全二叉树用一维数组保存后再转化为一个最小堆 代码如下(假如树中的数据都为整数) #include<stdio.h> int a[50]; int n; void swap(int p,int q){//交换函数 ... -
最小堆建立
2016-03-07 22:49:30题目来源:http://dsalgo.openjudge.cn/201409week5/2/最小堆建立题目:实现最小堆两个功能: 1、增加一个元素 2、输出并删除最小堆中的最小的数 输入: 第一行输入一个整数t,代表测试数据的组数。 对于每组... -
最小堆创建,排序。C语言实现
2018-12-12 09:52:10最小堆也叫优先队列,任何一个父节点都不大于左右子节点。 最小堆对应的有最大堆,区别在于父节点比子节点小还是大。 最小堆可以使用链表表示(需要三个指针),也可以用数组表示。 在这里只说明数组实现的最小堆... -
c: C++优先队列/priority_queue(最大堆、最小堆)
2020-04-04 16:47:08ref ...note 定义: priority_queue<int,vector,less> q;最大堆(默认为最大堆) priority_queue<int,vector,greater> q;最小堆 Priority queues are a type of c... -
最小堆 构建、插入、删除的过程图解
2016-05-21 00:47:02最小堆是一棵完全二叉树,非叶子结点的值不大于左孩子和右孩子的值。本文以图解的方式,说明 最小堆的构建、插入、删除的过程。搞懂最小堆的相应知识后,最大堆与此类似。 2.最小堆示例 3.最小堆的构建 ... -
c++使用vector建立最大堆和最小堆
2019-05-20 17:15:441. 建堆 vector<int> nums={6, 9, 2, 4, 7, 0, 1, 8, 3, 5}; 构建最大堆 make_heap(nums.begin(), nums.end()); //or make_heap(nums.begin(), nums.end(), less<int>()); 输出nums的结果为 9 8 2 6 7... -
最小堆的建立
2015-06-05 17:15:00最小堆的建立 -
算法入门--堆排序2(建立最小堆,从大到小)
2011-11-24 17:18:24#include #include int left(int i)//返回左孩子位置 { return 2*i; } ...void min_heapify(int *a,int heap_size,int i)//保持堆性质,使以i为根的子树成为最小堆 ,heap_size当前堆中元素数量 -
如何创建最小(大)堆(插入、删除)
2017-08-08 11:08:11我们要用1, 2, 5, 12, 7, 17, 25, 19, 36, 99, 22, 28, 46, 92来建立最小堆,并且删除最小的数,并增加一个数23 如何建立这个堆: //建堆 n = 0; for (int i = 1; i ) { n++; h[n] = a[n]; ...