Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

heap

Heap and priority queue:

A priority queue is an abstract data type, and a heap is a data structure, so a heap is not a priority queue, but a way to implement a priority queue.
There are many ways to implement a priority queue, such as arrays and linked lists. However, these implementations can only ensure that one of the insertion and deletion operations can be completed within the time complexity of O(1)O(1), while the other operation needs to be completed within the time complexity of O(N)O(N). A heap can make the insertion operation of the priority queue completed within the time complexity of O(log N)O(logN), and the deletion operation completed within the time complexity of O(log N)O(logN).

A heap is a special binary tree that satisfies the following conditions:

1. Complete binary tree (put nodes in order from left to right);
2. The value of each node must be greater than or equal to or less than or equal to the value of its child node.

Characteristics of the heap:

1. Elements can be inserted into the heap within the time complexity of O(logN);
2. Elements can be deleted from the heap within the time complexity of O(logN);
3. The maximum or minimum value in the heap can be obtained within the time complexity of O(1).

Classification of heaps:

Max heap: The value of each node in the heap is greater than or equal to the value of its child node. The top element (root node) of the max heap is the maximum value in the heap.
Minimum heap: The value of each node in the heap is less than or equal to the value of its child node. The top element (root node) of the minimum heap is the minimum value in the heap.
The current node is numbered i, the left child is numbered 2i, and the right child is numbered 2i+1.

Time complexity and space complexity

Heap Sort

Theory: Heap sort refers to sorting a set of unordered elements using the heap data structure.

The steps of the minimum heap sort algorithm are as follows:

Stack all elements into a minimum heap;
Take out and delete the top element of the heap, and place the top element of the heap in the data set T storing ordered elements;
At this point, the heap will be adjusted to a new minimum heap;
Repeat steps 3 and 4 until there are no elements in the heap;
At this time, a new data set T is obtained, in which the elements are arranged in ascending order.

The steps of the maximum heap sort algorithm are as follows:

Stack all elements into a maximum heap;
Take out and delete the top element of the heap, and place the top element of the heap in the data set T storing ordered elements;
At this point, the heap will be adjusted to the new maximum heap;
Repeat steps 3 and 4 until there are no elements in the heap;
At this time, a new data set T is obtained, in which the elements are arranged in descending order.
Time complexity: O(Nlog N). N is the number of elements in the heap.

Space complexity: O(N). N is the number of elements in the heap.