精华内容
下载资源
问答
  • python优先队列和堆的使用

    千次阅读 2019-07-25 12:33:50
    优先队列和堆(大顶堆小顶堆)经常被用来实现查找数组中最大或者最小的K个元素。之前一直使用C++对于C++的优先队列和堆比较熟悉,python的不太熟悉,这里进行记录。 1 优先队列 首先来看优先队列优先队列中的元素...

    0 前言

    优先队列和堆(大顶堆和小顶堆)经常被用来实现查找数组中最大或者最小的K个元素。之前一直使用C++对于C++的优先队列和堆比较熟悉,python的不太熟悉,这里进行记录。

    1 优先队列

    首先来看优先队列,优先队列中的元素是有优先级的,优先级高的元素排在前面。在python的中排序关键字小的排在前面。可以理解为排序关键字给出的是一个排名。 python3队列相关的模块在queue中,python2中的优先队列模块在Queue包中。
    存储内置数据类型:

    from Queue import PriorityQueue
    
    pq = PriorityQueue()
    
    for i in range(3,0,-1):
        pq.put(i)
    
    while not pq.empty():
        print pq.get()
    
    1 2 3
    

    存放元组:
    如果存放元组,则默认比较元组的第一个元素,小的在队列头部,如果,第一元素相同比较第二个元素,如果还相同依次往后比较。其实这应该是是内置的元组大小比较函数定义的比较方式。

    from queue import PriorityQueue
    
    pq = PriorityQueue()
    
    pq.put((1, 2))
    pq.put((1, 0))
    pq.put((2, 3))
    
    while not pq.empty():
        print (pq.get())
    

    存放自定义类型:
    自定义数据类型,需要自定义__cmp__或者__lt__比价函数。

    from queue import PriorityQueue
    class Job(object):
        def __init__(self, priority, description):
            self.priority = priority
            self.description = description
            print('New job:', description)
            return
     
        def __lt__(self, other):
            return self.priority < other.priority
     	''' 或者使用__cmp__函数
        def __cmp__(self, other):
            if self.priority < other.priority:
                return -1
            elif self.priority == other.priority:
                return 0
            else:
                return 1
        '''
    q2 = PriorityQueue()
     
    q2.put(Job(5, 'Mid-level job'))
    q2.put(Job(10, 'Low-level job'))
    q2.put(Job(1, 'Important job')) #数字越小,优先级越高
     
    while not q2.empty():
        next_job = q2.get() #可根据优先级取序列
        print('Processing job', next_job.description)
    
    ('New job:', 'Mid-level job')
    ('New job:', 'Low-level job')
    ('New job:', 'Important job')
    ('Processing job', 'Important job')
    ('Processing job', 'Mid-level job')
    ('Processing job', 'Low-level job')
    

    2 堆

    2.1 小顶堆

    python提供了heapq模块,提供了堆的支持,是基于python的list实现的。heapq提供的默认是一个小顶堆的实现,即最小的元素排在前面。
    堆(Heap)是一种特殊形式的完全二叉树,其中父节点的值总是大于子节点,根据其性质,Python 中可以用一个满足 heap[k] <= heap[2k+1] and heap[k] <= heap[2k+2] 的列表来实现(heapq 也确实是这么做的)
    下面介绍headp模块的使用:
    heapq模块中有6个函数:

    1、heappush(heap, x):向堆中添加元素

    from heapq import *
    heap = []
    for i in range(3):
        heappush(heap, i)
    print(heap)   #[0, 1, 2]
    heappush(heap, 0.5)
    print(heap)    #[0, 0.5, 2, 1]
    heappush(heap, 1.5) 
    print(heap)    #[0, 0.5, 2, 1, 1.5]
    

    2、heappop(heap):弹出堆中最小的元素,并且维持剩余元素的堆结构

    from heapq import *
    heap = []
    for i in range(3):
        heappush(heap, i)
    print(heap)   #[0, 1, 2]
    heappop(heap) #heappop函数会返回弹出的值
    print(heap)    #[1, 2]
    

    3、heapify(heap):将列表转换为堆

    from heapq import *
    heap = [5, 8, 0, 4, 6, 7]
    heapify(heap)
    print(heap)   #[0, 4, 5, 8, 6, 7]
    

    4、heapreplace(heap, x):弹出堆中最小的元素,然后将新元素插入。

    from heapq import *
    heap = [5, 8, 0, 4, 6, 7]
    heapify(heap)
    print(heapreplace(heap, 5.5)) #0
    print(heap)   #[4, 5.5, 5, 8, 6, 7]
    

    5、nlargest(n, iter)、nsmallest(n, iter):用来寻找任何可迭代对象iter中的前n个最大的或前n个最小的元素。

    from heapq import *
    lst = [5, 8, 0, 4, 6, 7]
    print(nsmallest(3, lst))
    print(nlargest(3, lst))
    

    2.2 大顶堆

    python没有提供大顶堆的实现,想要使用大顶堆需要一些trick。
    heappush(e)改为heappush(-e),heappop(e)为-heappop(e),也就是说存入和取出的数都是相反数,其他逻辑和TopK相同。
    按照这种思路自己封装一下就可以实现大顶堆。像优先队列一样,heapq同样支持自定义的数据类型,需要给自定义的数据类型定义__cmp__函数。

    参考文章:

    1. python使用heapq实现小顶堆(TopK大)/大顶堆(BtmK小)
    2. Python中的堆:heapq模块
    3. python中使用优先队列
    4. Python 的堆与优先队列 - PyTips 0x10
    展开全文
  • 优先队列和堆

    千次阅读 2019-07-26 19:45:33
    我们在学习优先队列之前我们先来看看他普通队列的区别 普通队列:先进先出,后进后出 优先队列:出队顺序入队顺序无关,优先级有关。动态选择优先级高的执行 不论是普通队列 还是优先队列,他们的本质还是...

    我们在学习优先队列之前我们先来看看他和普通队列的区别
    普通队列:先进先出,后进后出
    优先队列:出队顺序和入队顺序无关,和优先级有关。动态选择优先级高的执行
    不论是普通队列 还是优先队列,他们的本质还是一个队列 所以我们可以复用原来的队列的接口。我们也可以使用多种数据结构作为优先队列的底层实现结构,我们今天学的堆就是其中的一种底层实现结构。
    二叉堆(堆本身就是一颗二叉树)
    1.完全二叉树(把元素一层一层的放,知道放完为止)
    2.堆中某个节点的值总是不大于其父亲节点的值(最大堆)
    3…堆中某个节点的值总是不小于其父亲节点的值(最小堆)
    用数组存储二叉堆
    每个父亲节点的左孩子索引 = 父亲节点索引 * 2 +1;
    每个父亲节点的右孩子索引 = 父亲节点索引 * 2 + 2;
    每个父亲节点索引 = (孩子节点-1) / 2;
    要注意该节点有没有父亲节点,具体的实现代码如下

    public class MaxHeap<E extends Comparable<E>>  {
    	private Array<E> data;
    	public MaxHeap(int capacity) {
    		data = new Array<>(capacity);
    	}
    	public MaxHeap() {
    		data = new Array<>();
    	}
    	//返回堆中的元素个数
    	public int size() {
    		return data.getSize();
    	}
    	//返回一个布尔值,表示堆中是否为空
    	public boolean isEmpty() {
    		return data.isEmpty();
    	}
    //返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
    	private int parent(int index) {
    		if(index == 0) {
    			throw new IllegalArgumentException("索引为0,没有父亲节点");
    		}
    		return (index - 1) / 2;
    	}
    	//返回二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
    	private int leftChild(int index) {
    		return index * 2 + 1;
    	}
    	//返回二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
    	private int rightChild(int index) {
    		return index * 2 + 2;
    	}
    

    向堆中添加元素
    那么它只能是往最后面添加,添加时要注意满足堆的性质,该元素不能比他的父亲节点大,如果大于父亲节点那么不满足堆的性质,因此我们可以把这个节点和父亲节点替换一下,对应的替换完在与他的父亲节点进行比较以此类推,大于父亲节点就替换具体的实现代码如下:

    	//向堆中添加元素
    	public void add(E e) {
    		data.addLast(e);
    		siftUp(data.getSize() - 1);
    	}
    	private void siftUp(int k ) {
    		while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
    			data.swap(k, parent(k));
    			k = parent(k);
    		}
    	}
    

    从堆中取出元素(只能取出最大的元素)
    我们可以很容易的找到并取出最大的元素(数组下标为0),我们取出元素还要把它的左右子树有机结合在一起,所以我们需要把最后一个元素当做它的父亲节点,然后与左右孩子比较 看看是否大于左右孩子节点,如果小于则交换位置,交换完位置后还得继续与新的孩子节点进行比较,我们以此类推,最终达到了从堆中取出元素这种操作要注意最后一个元素顶替原来的根节点那么要注意让最后节点位置元素消失(二叉树不能有重复元素)还要注意二叉堆中是否有元素。具体的实现代码如下:

    	//看堆中的最大元素
    	public E findMax() {
    		if(data.getSize() == 0) {
    			throw new IllegalArgumentException("不能从空堆中找到最大的元素");
    		}
    		return data.get(0);
    	}
    	//取出堆中最大的元素
    	public E extractMax() {
    		E ret = findMax();
    		data.swap(0, data.getSize() - 1);
    		data.removeLast();
    		siftDown(0);
    		return ret;
    	}
    	private void siftDown(int k ) {
    		while(leftChild(k) < data.getSize()) {
    			int j = leftChild(k);
    			if(j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
    				j = rightChild(k);
    			}
    			//data[j] 是leftChild 和 rightChild 中的最大值
    			if(data.get(k).compareTo(data.get(j)) >= 0) {
    				break;
    			}
    			data.swap(k, j);
    			k = j;
    		}
    	}
    

    取出堆中的元素并替换成e,具体的实现代码如下:

    //取出堆中最大的元素,并且替换成元素e
    	public E replace(E e) {
    		E ret = findMax();
    		data.set(0, e);
    		siftDown(0);
    		return ret;
    	}
    

    将任意数组整理成堆的形状
    将数组看做完全二叉树,从倒数第一个非叶子节点来看从后往前进行下沉操作(交换父亲节点和孩子节点进行比较之后)他的位置只要获得最后一个元素的索引 根据上面的公式求出他的父亲节点即可具体实现代码如下

    //heapify操作
    	public MaxHeap(E[] arr) {
    		data = new Array<>(arr);
    		for(int i = parent(arr.length - 1); i >= 0; i-- ) {
    			siftDown(i);
    		}
    	}
    	public Array(E[] arr) {
    		data =(E[]) new Object[arr.length];
    		for(int i = 0; i < arr.length; i++) {
    			data[i] = arr[i];
    		}
    		size = arr.length;
    	}
    

    用堆实现优先队列(复用队列接口)
    具体实现代码如下

    public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
    	private MaxHeap<E> maxHeap;
    	public PriorityQueue() {
    		maxHeap = new MaxHeap<>();
    	}
    	@Override
    	public int getSize() {
    		return maxHeap.size();
    	}
    	@Override
    	public boolean isEmpty() {
    		return maxHeap.isEmpty();
    	}
    	@Override
    	public E getFront() {
    		return maxHeap.findMax();
    	}
    	@Override
    	public void enqueue(E e) {
    		maxHeap.add(e);
    	}
    	@Override
    	public E dequeue() {
    		return maxHeap.extractMax();
    	}
    }
    
    展开全文
  • 优先队列和堆的一些知识

    千次阅读 2017-06-29 09:56:12
    二叉

    1.概念

    优先队列:普通的队列具有先进先出的特性,元素追加在队尾,如果删除的话,从队头删除。而在优先队列中,队列中的数据被赋予了优先级。当访问元素时,优先级最高的会先被删除。所以说优先队列是最高级数据先出。
    :堆是指一个可以被看成一棵树的数组对象,堆总是满足下面两个性质:(1)堆中的某个节点必然小于(堆顶最大)或者大于(堆顶最小)其父节点的值;(2)所谓的堆呢,总是一棵完全二叉树。
    堆有序:当一棵二叉树的每个节点,都大于等于他的两个子节点时,它被称为堆有序。
    一棵大小为N的完全二叉树的高度为log2N+1(以2为底的)

    2.堆有序化的两种方式

    (1)由下至上的堆有序化
    如果一个堆有序,因为某个节点的变化,这个节点比它的父节点还要大的时候,那么我们就需要通过交换该节点和父节点的关系来修复堆的顺序。交换之后这个节点还有可能比它现在的父节点大,再次交换它和它当前父节点的位置,以此类推,一直到这个节点小于它的父节点为止。因此这个大根堆将被恢复有序。
    部分代码如下:

    private void swim(int k){
        while(k > 1 && K/2 < k){
            int temp = k/2;
            k/2 = k;
            k = temp;       
        }
    }

    (2)由上至下的堆有序化
    这种情况出现在和上面一种情况正好相反的状况中:在堆有序的状态下,因为某个节点小于它的两个子节点其中之一的时候,而顺序被打破。那么我们通过交换他和两个字节点中的较大者来将其恢复。这个节点在大根堆中处于一下向下移动的状态,因此形象的称之为“下沉”
    部分代码如下:

    private void sink(){
        while(2 * k <= N){
            int j = 2*k;
            if(j < N && j < j + 1) j++;
            if(!k < j) break;
            k = j;
        }
    }

    对于多叉堆的这些情况,同二叉堆。

    3.优先队列的对路归并问题

    有一个博主将的很不错
    http://www.cnblogs.com/songdechiu/p/6736114.html

    4.堆排序

    http://www.cnblogs.com/CherishFX/p/4643940.html

    展开全文
  • 优先队列和堆排序

    2016-09-06 23:00:15
    1. 从队列到优先队列: 无论栈还是队列,它们最重要最本质的操作都是入集合,出集合。队列是在队尾入队(插入),在队头出队(删除)。也即是说先出队的是先...2. 优先队列实现  在二叉的数组中,每个元素

    1.    从队列到优先队列:

    无论栈还是队列,它们最重要最本质的操作都是入集合,出集合。队列是在队尾入队(插入),在队头出队(删除)。也即是说先出队的是先入队的,那么存在这么一种情况,如果排队的人有着一种优先级(与排队顺序无关的优先级)那么我们就需要一种新的数据结构:优先队列。它需要插入操作和删除优先级最高的元素两种操作。,

    2.    优先队列的堆实现

        在二叉堆的数组中,每个元素都要保证大于等于另外两个特定位置的元素。可以用一个二叉树很好的表示即所有结点都大于等于它的子结点(如果有的话)。完全二叉树用数组就可以表示,因为索引可以把父子结点联系起来,向上一层,索引除以二,向下一层,索引是两倍或者两倍加一。

    3.    优先队列的对实现的核心操作

         我们的父子结点的大小关系和层层递进的父子关系结合起来维护了整个堆的有序,如果我们要插入元素,就必须放在合适的位置上才能继续维持有序,这显然需要移动。当我们将元素插入到最后一位之后(那个位置最小)应该将它向上层移动,直到它的父节点不小于它,这个操作我们称之为上浮。同时,另一个操作,删除最大的元素,最大的元素就是根节点,删除之后,我们将最后那个元素(最小的元素)放到顶端,让它向下层移动,我们可以用两个子节点中大的那个和它交换,直到它比两个子节点都大。

    4.    优先队列的堆实现步骤

          我们选用的数据结构是数组,索引可以描述这个数据结构,基于优先队列的操作是插入和删除最大的元素。,插入我们需要实现上浮操作。上浮操作其实就是基于条件判断的不断交换角标对应元素和角标除以二的元素。而删除最大的元素就是将最后一个元素放到第一个元素,然后实现下沉操作。下沉操作是角标对应元素和角标乘以二或者乘以二加一的元素交换直到条件适合为止。

    5.    优先队列的代码实现



     

    public class MaxPQ 
    {
    	private int n;
    	private int[] a;
    	public MaxPQ(int n)
    	{
    		a = new int[n+1];
    	}
    	public void insert(int x)
    	{
    		n++;
    		a[n] = x;
    		swim(n);
    	}
    	private void swim(int x)
    	{
    		while(x>1 && a[x/2]<a[x])
    		{
    			int t = a[x];
    			a[x] = a[x/2];
    			a[x/2] = t;
    			x = x/2;
    		}
    	}
    	public int delete()
    	{
    		int max = a[1];
    		a[1] = a[n];
    		n--;
    		sink(1);
    		return max;
    	}
    	private void sink(int x)
    	{
    		while(2*x <= n)
    		{
    			int y = 2*x;
    			if(2*y<n && y < y+1)
    			{
    				y++;
    			}
    			if(x >= y)
    				break;
    			int t = a[x];
    			a[x] = a[y];
    			a[y] = t;
    			x = y;
    		}
    	}
    }
    

    堆排序:

    如上所知,堆排序可以找出最大的元素,如果我们不断找出最大的元素放到最后面,然后恢复优先队列的结构,再进行,就可以实现排序。这个过程分为两个阶段,堆的构造阶段和下沉排序阶段。我们可以递归的调用sink()函数,从而构造起一个个小堆,进而完成整个堆的构造,第二个阶段是先把最大元素放在最后面,然后恢复堆。

    public class DuiSort
    {
    	private static void sink(int x,int[] a,int n)
    	{
    		while(2*x <= n)
    		{
    			int y = 2*x;
    			if(y<n && y < y+1)
    			{
    				y++;
    			}
    			if(x >= y)
    				break;
    			int t = a[x];
    			a[x] = a[y];
    			a[y] = t;
    			x = y;
    		}
    	}
    	public static void sort(int[] a)
    	{
    		int n = a.length;
    		for(int x=n/2; x>=1; x--)
    		{
    			sink(x,a,n);
    		}
    		while(n > 1)
    		{
    			int t = a[n];
    			a[n] = a[1];
    			a[1] = t;
    			n--;
    			sink(1,a,n);
    		}
    	}
    	public static void main(String[] args)
    	{
    		int[] arr = {0,4,5,8,7,6,9,3,1,2};
    		DuiSort.sort(arr);
    		for(int i=1; i<9 ; i++)
    		{
    			System.out.println(arr[i]);
    		}
    	}
    }
    

    代码没调好,改天慢慢调。。

     

     

    展开全文
  • 二叉堆分为两种,最小堆和最大堆。最小堆是父节点的键值总是小于等于子节点的键值。最大堆是父节点的键值总是大于等于子节点的键值。 可以将二叉堆看成数组的形式。 代码: // 模拟最小堆 //
  • Java优先队列)理解使用

    千次阅读 2021-06-09 20:51:44
    什么是优先队列) Java中的使用(小根为例)
  • 优先队列是出队顺序入队顺序无关,优先级相关。(如:医院看病时,病情最严重的那个需要先看病)  实现优先队列同样底层也可以选择多种数据结构, 选择 普通的线性结构实现:出队O(1),入队O(n); 选择 顺序...
  • 优先队列:出队顺序入队顺序无关,优先级有关。动态选择优先级高的执行 普通队列:先进先出,后进后出 的概念: 即用完全二叉树来维护的一组数据。 一般的,进行一次操作的时间复杂度在O(1)~O(logn)之间...
  • 堆和优先队列

    千次阅读 多人点赞 2018-08-09 17:29:59
    优先队列和其实是队列的一种 普通队列:先进先出;后进先出 优先队列:出队顺序入队顺序无关;优先级相关 优先队列的接口普通队列的接口是完全相同的,只是在出队查看队首的实现方式会不同(优先级最高...
  • 优先队列: 说到底还是一种队列 不过是一种特殊的队列 他的工作就是poll()/peek()出队列中最大/最小的那个元素 : 首先我们要明确:是一个很大的概念 他并不一定是完全二叉树 我们之前用完全二叉树是因为这个很...
  • 目录0 优先队列1 最大优先队列2 最小优先队列 0 优先队列 普通队列先进先出,队尾加,队头删; 某些情况下,我们需要找出队列中的最大值或最小值。比如使用一个队列保存计算机的任务,任务需要有优先级,我们需要找...
  • 的 python 实现,的基本原理
  • 二叉查找树是以一种特殊的二叉树...  遍历元素:遍历主要有中序、前序、后序、深度优先、广度优先等。  下面这个类包括了结点的定义还有二叉树的定义。 package binaryTree; public class BinaryTree {  //
  • 主要介绍了python 堆和优先队列的使用详解,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  •  优先队列就是具备优先级的队列,优先级可以用队列里面的值大小表示,也就是值越大表示的优先级越高,所以,优先队列就是可以删除最大元素插入元素的队列。 2.什么是  又称为二叉,二叉是一组能够用...
  • 优先队列和堆优先队列支持两种操作:删除最大元素插入元素。可以用有序或者无序数组完成这个数据结构,但是用二叉(以下简称)可以更加快速地完成元素的删除插入。的插入删除元素的最大数量级都是...
  • 三种方法:暴力、分治、最小优先队列) 暴力解法有两种,一种是12排,然后3,然后4,继续下去; 另一种是先放到一个数组中进行排序,然后按照顺序连接 分而治之:两两合并 如果有k个链表,平均每个链表有n个...
  • Java优先队列的实现

    2018-10-31 17:14:16
    数据结构与算法第六章,优先队列,heap_maximum 返回优先队列的最大值 heap_extract_max 删除并返回最大值 max_heap_insert插入值为key的元素进优先队列中 。
  • 队列和优先队列(Priority Queue) 队列是一种可以完成插入删除的数据结构。普通队列是先进先出(FIFO), 即先插入的先被删除。 然而在某些时候我们需要按照任务的优先级顺序来决定出队列的顺序,这个时候就需要...
  • Java 优先队列

    2019-04-16 21:37:15
    优先队列:出队顺序入队顺序无关;优先级有关。 入队与普通队列一样,不过不同在出队这里。 动态选择优先级高的任务进行执行。 举个例子:比如医院中的病人,医生不可能知道直接对医院中的病人进行优先级进行...
  • 主要介绍了java编程实现优先队列的二叉代码分享,具有一定参考价值,需要的朋友可以了解下。
  • C++ 优先队列实现最大堆和最小堆 优先级队列 template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue; C++ STL实现的...
  • 使用排序实现优先队列

    千次阅读 2019-07-12 11:55:59
    二叉:是一组能用有序的完全二叉树排序的元素,并在数组中按照二叉树的层序遍历顺序保存。 如果要将上图的二叉元素(节点数为N)保存在数组中,则需要创建一个长为N+1的数组,第0个元素不用,使用[1~N]保存...
  • STL中优先队列自定义最大最小引言最大的一个例子最小的一个例子 引言 在算法实践中,有的算法要求不停地插入或移除最大或最小值。若用线性比较,则时间复杂度为O(n2n^2n2)。这时候,若用优先队列,...
  • 实现方式:有序表或无序表(即数组,或顺序表和链表)、二叉树、AVL平衡二叉树、堆和二叉堆。使用普通的表实现优先队列的性能比较低,有序表插入为O(1),无序表取出为O(n),另外使用普通二叉树实现优先队列只能
  • 优先队列(Priority Queue)是一种数据结构,它支持插入(Insert)操作删除最小值(DeleteMin)或删除最大值(DeleteMax)并返回删除元素操作。 优先队列的这些操作等价于队列的EnQueueDeQueue操作。区别在于,对于优先...
  • 什么是优先队列? 普通队列:先进先出,后进后出 优先队列:出队顺序入队顺序无关;...普通的线性结构和堆都可以作为优先队列的底层实现。 实现优先队列,在最坏的情况下,入队与出队的操作...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 75,901
精华内容 30,360
关键字:

优先队列和堆