Heap, stack, queue

Pile up

It's a binary tree , The value of each of its parent nodes will only be less than or equal
On all child nodes （ Value ）.
• It uses arrays to implement ： Count from zero , For all k ,
There are heap[k] <= heap[2k+1] and heap[k] <= heap[2k+2].
• The most interesting feature of heap is that the smallest element is always at the root node ：heap[0].

function	describe
heapq.heapify(x)	take list x Into piles
heapq.heappush(heap, item	take item Add the value of heap in , Keep the heap invariant .
heapq.heappop(heap)	Pop up and return heap The smallest element of , Keep the heap invariant . Use heap[0] , You can access only the smallest element without popping it up .

heapq.heappushpop(heap, item)
• take item Put in a pile , And then pop up and go back
heap The smallest element of .
• The heap size remains the same .
• Put it in first 、 Pop it up again

Interactive function ：
heapq.heapreplace(heap, item)
• Pop up and return heap The smallest of all ,
And push in New item.
• The size of the heap doesn't change .
• First pop up one , Put one more
• Replace and then sort

The generic function ：
heapq.merge(*iterables)
Merge multiple sorted inputs into one sorted output （ for example ,
Merge time stamped entries from multiple log files ）. Return to scheduled
Ordinal valued iterator.
heapq.nlargest(n, iterable)
from iterable The defined dataset is returned before n The largest elements
A list of .
heapq.nsmallest(n, iterable)
from iterable The defined dataset is returned before n Composed of the smallest elements
A list of .

practice ：
Build a heap ：
• Delete the smallest value ;
• Add a value to it ;

import heapq
x=[1,2,3,4,6,7,9,14,15,17,23,36,0]
heapq.heapify(x)
print(x)
heapq.heappop(x)
print(x)
heapq.heappush(x,8)# The previous heap has changed , This change is the result of the last time 
print(x)

Running results ：
[0, 2, 1, 4, 6, 3, 9, 14, 15, 17, 23, 36, 7]
[1, 2, 3, 4, 6, 7, 9, 14, 15, 17, 23, 36]
[1, 2, 3, 4, 6, 7, 9, 14, 15, 17, 23, 36, 8]

Stacks and queues ：

queue ：

principle ： fifo
Application scenarios
• Historical record ： First generated , Discard at the earliest
• The data backup ： First generated , Discard first
• Printer control
• CPU Distribution, etc

Realization ：

from collections import deque # Need to import 
x=deque([9,7,8])
print(x)
x.append(666)
print(x)
x.popleft() # No parameters , The function defines the execution from the left 
print(x)

Output results ：
deque([9, 7, 8])
deque([9, 7, 8, 666])
deque([7, 8, 666])

Stack ：
principle ： Last in, first out
Application scenarios ：
• Operation fallback ：Ctrl+Z
• Database system and other scenarios
• The browser goes back to the previous page
• Parentheses matching

Realization ：

x=[9,7,8]
print(x)
x.append(666)
print(x)
x.pop()
print(x)

Running results ：
[9, 7, 8]
[9, 7, 8, 666]
[9, 7, 8]