当前位置:网站首页>Priority queue (heap)
Priority queue (heap)
2022-07-06 00:01:00 【Snail at the end of the pyramid】
Catalog
The sequential storage of binary trees
storage
Use array to save binary tree structure , Method is to put the binary tree into the array by sequence traversal .
Generally, it is only suitable for representing complete binary tree , Because incomplete binary trees will waste space .
The main use of this method is the representation of the heap .
Subscript relation
- Known parents (parent) The subscript , be :
Left the child (left) Subscript = 2 * parent + 1;
The right child (right) Subscript = 2 * parent + 2; - Known child ( There's no distinction between left and right )(child) Subscript , be :
Parents (parent) Subscript = (child - 1) / 2;
Pile up
Concept
- The heap is logically a complete binary tree
- The heap is physically stored in an array
- Satisfy that the value of any node is greater than the value of the node in its subtree , It's called a lot of , Or a big pile , Or the largest heap . conversely , It's a small pile , Or a small pile of roots , Or the smallest heap .
Basic operation
Building the heap
public void creatBigHeap(int[] array) {
for(int i=0;i<array.length;i++) {
elem[i]=array[i];
usedSize++;
}
for(int parent=(usedSize-1-1)/2;parent>=0;parent--) {
// adjustment
shiftDown(parent,usedSize);
}
}
//parent: The root node of each tree len: The end position of each tree adjustment
public void shiftDown(int parent,int len) {
int child=2*parent+1;
while(child < len) {
if( child+1 < len &&elem[child] < elem[child+1]) {
child++;// Ensure the current subscript of the maximum value of the left and right children
}
if(elem[child] > elem[parent]) {
int tmp=elem[child];
elem[child]=elem[parent];
elem[parent]=tmp;
parent=child;
child=2*parent+1;
}else {
break;
}
}
}
The team
// Queue entry ( Take a large pile as an example )
public void offer(int val) {
if(isFull()) {
// Capacity expansion
elem=Arrays.copyOf(elem, elem.length *2);
}
elem[usedSize]=val;
usedSize++;
// Notice what's coming in here usedSize-1
shiftUp(usedSize-1);
}
public boolean isFull() {
return usedSize==elem.length;
}
// Adjust up
public void shiftUp(int child) {
int parent=(child-1)/2;
while(child >0) {
if(elem[child] > elem[parent]) {
int tmp=elem[child];
elem[child]=elem[parent];
elem[parent]=tmp;
child=parent;
parent=(child-1)/2;
}else {
break;
}
}
}
Out of the team
// Out of the team
public int poll() {
if(isEmpty()) {
throw new RuntimeException(" Priority queue is empty ");
}
int tmp=elem[0];
elem[0]=elem[usedSize-1];
elem[usedSize-1]=tmp;
usedSize--;
shiftDown(0,usedSize);
// Return the element to be dequeued
return tmp;
}
public boolean isEmpty() {
return usedSize==0;
}
public void shiftDown(int parent,int len) {
int child=2*parent+1;
while(child < len) {
if( child+1 < len &&elem[child] < elem[child+1]) {
child++;// Ensure the current subscript of the maximum value of the left and right children
}
if(elem[child] > elem[parent]) {
int tmp=elem[child];
elem[child]=elem[parent];
elem[parent]=tmp;
parent=child;
child=2*parent+1;
}else {
break;
}
}
}
Get team leader elements
// Get team leader elements
public int peek() {
if(isEmpty()) {
throw new RuntimeException(" Priority queue is empty ");
}
return elem[0];
}
top-K problem
Heap sort
public void heapSort() {
int end=usedSize-1;
while(end>0) {
int tmp=elem[0];
elem[0]=elem[end];
elem[end]=tmp;
shiftDown(0,end);
end--;
}
}
边栏推荐
- 云呐|公司固定资产管理系统有哪些?
- What are Yunna's fixed asset management systems?
- 【DesignMode】装饰者模式(Decorator pattern)
- 时区的区别及go语言的time库
- What is information security? What is included? What is the difference with network security?
- 4 points tell you the advantages of the combination of real-time chat and chat robots
- Fiddler Everywhere 3.2.1 Crack
- Yunna | what are the main operating processes of the fixed assets management system
- Key structure of ffmpeg - avframe
- What are the functions of Yunna fixed assets management system?
猜你喜欢
Mathematical model Lotka Volterra
How to get all the values stored in localstorage
Gd32f4xx UIP protocol stack migration record
关于结构体所占内存大小知识
MySql——CRUD
Fiddler Everywhere 3.2.1 Crack
零犀科技携手集智俱乐部:“因果派”论坛成功举办,“因果革命”带来下一代可信AI
The difference of time zone and the time library of go language
云呐|公司固定资产管理系统有哪些?
时区的区别及go语言的time库
随机推荐
Zero rhino technology joined hands with the intelligence Club: the "causal faction" forum was successfully held, and the "causal revolution" brought the next generation of trusted AI
Doppler effect (Doppler shift)
C reflection and type
【NOI模拟赛】Anaid 的树(莫比乌斯反演,指数型生成函数,埃氏筛,虚树)
FFT 学习笔记(自认为详细)
Zhuan: in the future, such an organization can withstand the risks
Qt 一个简单的word文档编辑器
What is a humble but profitable sideline?
CloudCompare&PCL 点云随机添加噪声
[gym 102832h] [template] combination lock (bipartite game)
Asynchronous task Whenall timeout - Async task WhenAll with timeout
4 points tell you the advantages of the combination of real-time chat and chat robots
Senparc.Weixin.Sample.MP源码剖析
Tools to improve work efficiency: the idea of SQL batch generation tools
【DesignMode】装饰者模式(Decorator pattern)
MySql——CRUD
权限问题:source .bash_profile permission denied
Determinant learning notes (I)
【GYM 102832H】【模板】Combination Lock(二分图博弈)
Wechat applet -- wxml template syntax (with notes)