Home Backend Development Python Tutorial What are the usage scenarios of heap and priority queue in Python?

What are the usage scenarios of heap and priority queue in Python?

Oct 28, 2023 am 08:56 AM
heap scenes to be used priority queue

What are the usage scenarios of heap and priority queue in Python?

What are the usage scenarios of heap and priority queue in Python?

Heap is a special binary tree structure that is often used to efficiently maintain a dynamic collection. The heapq module in Python provides a heap implementation and can easily perform heap operations.

Priority queue is also a special data structure. Different from ordinary queues, each element of it has a priority associated with it. The highest priority element is taken out first. The heapq module in Python can also implement the priority queue function.

Below we introduce some specific scenarios of using heaps and priority queues, and give relevant code examples.

  1. Finding the Top K problem
    It is a common problem to solve the first k largest or smallest elements in a sequence, such as solving the first k largest numbers or the first k smallest numbers. . This problem can be easily solved using a heap of size k or a priority queue.
import heapq

def top_k_smallest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap

nums = [5, 3, 8, 2, 7, 1, 9]
k = 3
result = top_k_smallest(nums, k)
print(result)  # 输出 [3, 2, 1]
Copy after login
  1. Merge ordered arrays
    It is a common problem to merge multiple ordered numbers to form an ordered array. It can be implemented using a priority queue. Each time, the smallest element is taken from each array and put into the priority queue, and then the elements in the queue are taken out in turn.
import heapq

def merge_sorted_arrays(arrays):
    result = []
    pq = []
    for array in arrays:
        if array:
            heapq.heappush(pq, (array[0], array))
    
    while pq:
        smallest, array = heapq.heappop(pq)
        result.append(smallest)
        if array[1:]:
            heapq.heappush(pq, (array[1], array[1:]))
    
    return result

arrays = [[1, 3, 5], [2, 4, 6], [0, 7, 8]]
result = merge_sorted_arrays(arrays)
print(result)  # 输出 [0, 1, 2, 3, 4, 5, 6, 7, 8]
Copy after login
  1. Finding the median
    Finding the median of a sequence is a classic problem. This can be achieved using two heaps, a max heap for the first half of the sequence and a min heap for the second half of the sequence. Keeping the sizes of the two heaps equal or different by one, the median can be taken at the top of the heap.
import heapq

def median(nums):
    min_heap = []
    max_heap = []
    for num in nums:
        if len(max_heap) == 0 or num <= -max_heap[0]:
            heapq.heappush(max_heap, -num)
        else:
            heapq.heappush(min_heap, num)
        
        if len(max_heap) > len(min_heap) + 1:
            heapq.heappush(min_heap, -heapq.heappop(max_heap))
        elif len(min_heap) > len(max_heap):
            heapq.heappush(max_heap, -heapq.heappop(min_heap))
    
    if len(max_heap) > len(min_heap):
        return -max_heap[0]
    elif len(min_heap) > len(max_heap):
        return min_heap[0]
    else:
        return (-max_heap[0] + min_heap[0]) / 2

nums = [4, 2, 5, 7, 1, 8, 3, 6]
result = median(nums)
print(result)  # 输出 4.5
Copy after login

The above are some common usage scenarios and sample codes of heap and priority queue in Python. Heaps and priority queues are some commonly used data structures, and mastering their use is very helpful for solving some complex problems.

The above is the detailed content of What are the usage scenarios of heap and priority queue in Python?. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

The differences and usage scenarios between Redis and MongoDB The differences and usage scenarios between Redis and MongoDB May 11, 2023 am 08:22 AM

Redis and MongoDB are both popular open source NoSQL databases, but their design concepts and usage scenarios are different. This article will focus on the differences and usage scenarios of Redis and MongoDB. Introduction to Redis and MongoDB Redis is a high-performance data storage system that is often used as cache and message middleware. Redis uses memory as the main storage medium, but it also supports persisting data to disk. Redis is a key-value database that supports a variety of data structures (such as

The differences and usage scenarios between Redis and Elasticsearch The differences and usage scenarios between Redis and Elasticsearch May 11, 2023 am 08:01 AM

Differences and Usage Scenarios between Redis and Elasticsearch With the rapid development and massive quantification of Internet information, efficient storage and retrieval of data has become more and more important. For this reason, NoSQL (NotOnlySQL) type databases have emerged, among which Redis and Elasticsearch are more popular. This article will compare Redis and Elasticsearch and explore their usage scenarios. Redis and Elasticsearch

Detailed explanation of priority queue implementation in Redis Detailed explanation of priority queue implementation in Redis Jun 20, 2023 am 08:31 AM

Detailed explanation of Redis implementation of priority queue Priority queue is a common data structure that can sort elements according to certain rules and maintain this order during queue operations, so that elements taken out of the queue always follow the preset priority conduct. As an in-memory database, Redis also has advantages in implementing priority queues because of its fast and efficient data access capabilities. This article will introduce in detail the method and application of Redis to implement priority queue. 1. Basic principles of Redis implementation Basic principles of Redis implementation of priority queue

What is the difference between heap and stack What is the difference between heap and stack Nov 22, 2022 pm 04:12 PM

Differences: 1. The heap space is generally allocated and released by the programmer; while the stack space is automatically allocated and released by the operating system. 2. The heap is stored in the second-level cache, and the life cycle is determined by the garbage collection algorithm of the virtual machine; while the stack uses the first-level cache, which is usually in the storage space when it is called, and is released immediately after the call is completed. 3. The data structures are different. Heap can be regarded as a tree, while stack is a first-in, last-out data structure.

Deque in Python: Implementing efficient queues and stacks Deque in Python: Implementing efficient queues and stacks Apr 12, 2023 pm 09:46 PM

deque in Python is a low-level, highly optimized deque useful for implementing elegant and efficient Pythonic queues and stacks, which are the most common list-based data types in computing. In this article, Mr. Yun Duo will learn the following together with you: Start using deque to effectively pop up and append elements. Access any element in deque. Use deque to build an efficient queue. Start using deque to append elements to the right end of a Python list and pop up elements. The operations are generally very Efficient. If time complexity is expressed in Big O, then we can say that they are O(1). And when Python needs to reallocate memory to increase the underlying list to accept new elements, these

The difference between heap and stack The difference between heap and stack Jul 18, 2023 am 10:17 AM

The difference between heap and stack: 1. The memory allocation method is different. The heap is manually allocated and released by the programmer, while the stack is automatically allocated and released by the operating system. 2. The size is different. The size of the stack is fixed, while the stack is automatically allocated and released by the operating system. The size of is growing dynamically; 3. Data access methods are different. In the heap, data access is achieved through pointers, while in the stack, data access is achieved through variable names; 4. Data life cycle , In the heap, the life cycle of data can be very long, while in the stack, the life cycle of variables is determined by the scope in which they are located.

What are the differences between java heap and stack What are the differences between java heap and stack Dec 25, 2023 pm 05:29 PM

The difference between Java heap and stack: 1. Memory allocation and management; 2. Storage content; 3. Thread execution and life cycle; 4. Performance impact. Detailed introduction: 1. Memory allocation and management. The Java heap is a dynamically allocated memory area, mainly used to store object instances. In Java, objects are allocated through heap memory. When an object is created, the Java virtual machine Allocate corresponding memory space on the system, and automatically perform garbage collection and memory management. The size of the heap can be dynamically adjusted at runtime, configured through JVM parameters, etc.

Heap and priority queue in C++ Heap and priority queue in C++ Aug 22, 2023 pm 04:16 PM

Heap and priority queue are commonly used data structures in C++, and they both have important application value. This article will introduce and analyze the heap and priority queue respectively to help readers better understand and use them. 1. Heap is a special tree data structure that can be used to implement priority queues. In the heap, each node satisfies the following properties: its value is not less than (or not greater than) the value of its parent node. Its left and right subtrees are also a heap. We call a heap that is no smaller than its parent node a "min-heap" and a heap that is no larger than its parent node a "max-heap"

See all articles