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:37

PlotWizard

Recent works View more works>>

Data Structures and Algorithms Applications of Heaps

PlotWizard

Recent works View more works>>

Recommended to you
Outline

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.