MindMap Gallery Data Structures and Algorithms Applications of Heaps
Data structure and algorithm: Application of heap, which is an application of binary tree in data structure budget method. This map includes three parts: priority queue, finding TOP K problem, and finding median.
Edited at 2021-07-16 19:10:37Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
Heap applications
priority queue
definition
First is a queue
The dequeuing order is not FIFO, but dequeuing according to priority.
application
1. Merge ordered files
definition
N ordered small files, merge them into a large file and ensure the order
General method:
Each time, take out the smallest one from all the files (because it is ordered, so it is at the beginning or the end), put it into an array for sorting, and put the final content into the large file.
Use heap:
At the beginning, use the smallest one in each file to create a small top heap, then delete the top elements of the heap and put them into the large file, then take out the smallest insertion heap from each file in turn, and then delete the paired elements and put them into the big file. Put it into a large file, and so on, until all small files are fetched and the heap elements are deleted.
2. High performance timer
General method:
Fixed time interval polling timer to determine status
Use heap:
Maintain a small top heap based on the remaining time to start the task. Then the next time the task is executed is the remaining time of the top heap timer. There is no need to poll.
Asking for Top K questions
definition:
Find the largest/smallest N data from some data
static data
Taking the maximum N number as an example, create a small top heap containing N pieces of data, take out the data in turn, and compare it with the top element of the small top heap:
If it is greater than the top element of the heap, delete the top element of the heap and insert the data
If it is less than the top element of the heap, no processing is done
The final desired data set is the data in the heap
dynamic data
The data is dynamic, so a heap is always maintained (if you want the maximum K, you will build a small top heap, if you want the minimum K, you will build a big top heap). Every time new data is added, it will be compared with the top elements of the heap. Determine whether to insert into the heap
Summary: Build a big pile or a small pile?
According to the characteristics of the heap, the element at the top of the heap is either the largest or the smallest. When seeking the maximum K, most of the data in the heap must be larger than the top of the heap. That is, build a big heap, otherwise build a small heap.
Find the median
static data
The amount of data is small and the memory is sufficient: put it in the array, sort it, and take the middle data
The amount of data is large and the memory is not enough:
dynamic data
1. Use two heaps, a large top heap and a small top heap; the large top heap stores small data, and the small top heap stores large data. All data in the small top heap is larger than that of the large top heap.
2. Dynamically maintain two heaps so that their numbers are equal or differ by 1.
1. When a new data comes in, if the data is larger than the top element of the big top heap, insert it into the small top heap, and then determine the number of the two heaps. If there are too many small top heaps, delete the top element of the small top heap. Drop, insert the big top pile
2. When a new piece of data comes in, if the data is smaller than the top element of the big top heap, insert it into the big top heap. Then it is judged whether the number of small top heaps exceeds. If it exceeds, the top element of the heap is removed and inserted into the small top heap. top pile
Expand
The median is actually the number at the 50% position. This 50% can be replaced by another number, such as 99% of the 99% response time.