当前位置:网站首页>Heap, stack, queue
Heap, stack, queue
2022-07-06 15:09:00 【Naive code writing】
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]
边栏推荐
- UCORE lab2 physical memory management experiment report
- Logstack introduction and deployment -- elasticstack (elk) work notes 019
- UCORE lab7 synchronous mutual exclusion experiment report
- Functions: Finding Roots of equations
- 软件测试有哪些常用的SQL语句?
- To brush the video, it's better to see if you have mastered these interview questions. Slowly accumulating a monthly income of more than 10000 is not a dream.
- 软件测试工作太忙没时间学习怎么办?
- 安全测试入门介绍
- Login the system in the background, connect the database with JDBC, and do small case exercises
- Transplant hummingbird e203 core to Da Vinci pro35t [Jichuang xinlai risc-v Cup] (I)
猜你喜欢
后台登录系统,JDBC连接数据库,做小案例练习
王爽汇编语言学习详细笔记一:基础知识
Investment operation steps
"If life is just like the first sight" -- risc-v
ucore lab2 物理内存管理 实验报告
Leetcode simple question: check whether the numbers in the sentence are increasing
Express
Keil5-MDK的格式化代码工具及添加快捷方式
Nest and merge new videos, and preset new video titles
Cadence physical library lef file syntax learning [continuous update]
随机推荐
UCORE lab2 physical memory management experiment report
Global and Chinese market of pinhole glossmeter 2022-2028: Research Report on technology, participants, trends, market size and share
Opencv recognition of face in image
ucore lab1 系统软件启动过程 实验报告
Build your own application based on Google's open source tensorflow object detection API video object recognition system (I)
Function: find 1-1/2+1/3-1/4+1/5-1/6+1/7-... +1/n
Cc36 different subsequences
数字电路基础(二)逻辑代数
Global and Chinese market of portable and handheld TVs 2022-2028: Research Report on technology, participants, trends, market size and share
Global and Chinese market of DVD recorders 2022-2028: Research Report on technology, participants, trends, market size and share
Detailed introduction to dynamic programming (with examples)
CSAPP homework answers chapter 789
China's county life record: go upstairs to the Internet, go downstairs' code the Great Wall '
Don't you even look at such a detailed and comprehensive written software test question?
How to solve the poor sound quality of Vos?
pytest
What is an index in MySQL? What kinds of indexes are commonly used? Under what circumstances will the index fail?
自动化测试中敏捷测试怎么做?
CSAPP家庭作业答案7 8 9章
王爽汇编语言详细学习笔记二:寄存器