Heap sort algorithm popularization tutorial

[[121962]]

Reference for this article: Introduction To Algorithms, second edition.

In this article, we are going to talk about the heap sort algorithm. As far as I know, to really understand an algorithm thoroughly, the best way is to find the original paper or related literature of this algorithm.

Ok, let’s start this section.

1. Basic characteristics of heap sort algorithm

Time complexity: O(nlgn)...

// Equivalent to merge sort

Worst case: O(nlgn)

Space complexity: O(1).

Unstable.

2. Establishment of heap and *** heap

To introduce the heap sort algorithm, we must first start with the introduction of the heap, then build the *** heap, and then talk about the heap sort algorithm.

2.1. Introduction to Heap

As shown below,

a), is a heap, which can be regarded as a complete binary tree.

Each heap corresponds to an array b). Suppose an array A of a heap,

We use length[A] to represent the number of elements in the array, and heap-size[A] to represent the number of elements in the heap itself stored in A.

Of course, heap-size[A]<=length[A].

The root of the tree is A[1], i represents the subscript of a node,

The parent node is PARENT(i), the left child LEFT[i], and the right child RIGHT[i] have the following relationship:

PARENT(i)

return |_i/2_|

LEFT(i)

return 2i

RIGHT(i)

return 2i + 1

Binary heaps are divided into minimum heaps and minimum heaps based on the size comparison between the root node and its child nodes.

***heap:

Each node i other than the root is no greater than its root node, that is, the root is the *** element, at the top, there is

A[PARENT(i)] (root) ≥ A[i] ,

Minimum heap:

Each node i other than the root is not less than its root node, that is, the root is the smallest element, at the top, there is

A[PARENT(i)] (root) ≤ A[i] .

In the heap sort algorithm of this section, we use the minimum heap; the minimum heap is usually used when constructing a minimum priority queue.

As mentioned above, a heap can be viewed as a tree, so the height of the heap is the height of the tree, O(lgn).

Therefore, for general operations, the running time is O(lgn).

Specifically, as follows:

The MAX-HEAPIFY: O(lgn) This is the key to maintaining a *** heap.

The BUILD-MAX-HEAP: Linear time. Constructs a MAX heap from an unordered input array.

The HEAPSORT: O(nlgn) time, the heap sort algorithm sorts an array in-place.

The MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY, HEAP-MAXIMUM: O(lgn).

The heap can be used as a minimum priority queue.

2.2.1. Maintaining the properties of the heap (O(lgn))

In order to maintain the properties of a heap, we use the MAX-HEAPIFY operation, make adjustments, and recursively call this operation to make the subtree with i as the root a heap.

The MAX-HEAPIFY algorithm is as follows (core):

 MAX-HEAPIFY(A, i)
 l ← LEFT(i)
 r ← RIGHT(i)
 if l ≤ heap-size[A] and A[l] > A[i]
 then largest ← l
 else largest ← i
 if r ≤ heap-size[A] and A[r] > A[largest]
 then largest ← r
 if largest ≠ i
    then exchange A[i] <-> A[largest]
         MAX-HEAPIFY(A, largest)

As mentioned above, first, in the first step, find the largest element among the corresponding array element A[i], the left child A[LEFT(i)], and the right child A[RIGHT(i)], and store its subscript in largest. If A[i] is already the largest element, the program ends directly. Otherwise, if a child node of i is the largest element, swap it, that is, A[largest] with A[i], so that i and its children can satisfy the largest heap property. The element pointed to by the subscript largest becomes the value of A[i], which violates the largest heap property, so MAX-HEAPIFY is called on the element pointed to by largest. The following is a demonstration of this MAX-HEAPIFY process (the figure below adjusts 4 to the largest layer, a one-time operation, but the exploration time is LogN):

From the above figure, we can easily see that after the initial construction of a heap, the element A[i], that is, 16, is greater than its two child nodes 4 and 10, which satisfies the heap property. Therefore, i points downward to 4, which is less than the left child 14, so MAX-HEAPIFY is called to swap the position of 4 with its child 14. But after 4 is in the original position of 14, 4 is less than its right child 8, which violates the heap property, so MAX-HEAPIFY is recursively called again to swap the positions of 4 and 8. Thus, the heap property is satisfied and the program ends.

2.2.2 Running time of MAX-HEAPIFY

When MAX-HEAPIFY is applied to a subtree of size n rooted at node i, its running time is the time taken to adjust the relationship between elements A[i], A[LEFT(i)], and A[RIGHT(i)] (O(1), plus the time required to call MAX-HEAPIFY on the subtree rooted at one of the children of i, and the size of the subtree of node i is at most 2n/3, so the running time of MAX-HEAPIFY is

T (n) ≤ T(2n/3) + Θ(1).

We can prove that the recursive solution of this formula is T(n)=O(lgn). For the specific proof, please refer to Section 6.2 of Chapter 6 of Introduction to Algorithms, which is omitted here.

2.3.1. Building a heap (O(N))

BUILD-MAX-HEAP(A)

 heap-size[A] ← length[A]
 for i ← |_length[A]/2_| downto 1
 do MAX-HEAPIFY(A, i) //Build a heap. How to build a column? It turns out that MAX-HEAPIFY(A, i) is called continuously to build a *** heap.  

BUILD-MAX-HEAP calls MAX-HEAPIFY once for each other node.

To build a *** heap corresponding to the array A[1...n]. The elements in A[(|_n/2_|+1) ‥ n] are all leaves in the tree.

Therefore, naturally, each node can be regarded as a heap containing only one element.

For the correctness of this process BUILD-MAX-HEAP(A), please refer to Section 6.3 of Chapter 6 of Introduction to Algorithms.

The following figure is an example of this process (the following figure continuously calls the MAX-HEAPIFY operation to adjust all the numbers that violate the heap properties, a total of N operations, however, the exploration time is finally precisely O(N)):

2.3.2. BUILD-MAX-HEAP running time

Since each call to MAX-HEAPPIFY takes O(lgn) time, and there are O(n) calls in total, the simple upper bound of BUILD-MAX-HEAP is O(nlgn). The book Introduction to Algorithms mentions that although this time bound is correct, it is not precise enough in an asymptotic sense.

So, how many columns are there for a more precise time boundary?

Since MAX-HEAPIFY takes different amounts of time to run at nodes of different heights in the tree, and most nodes have relatively small heights,

We know that the height of a heap of n elements is |_lgn_| (rounded down), and at any height h, there are at most |-n/2^h+1-| (rounded up) nodes.

Therefore, the time it takes for MAX-HEAPIFY to act on a node of height h is O(h), so the upper bound of BUILD-MAX-HEAP is: O(n). The specific derivation process is omitted.

3. Heap sort algorithm

The so-called heap sort is to call the above two processes: a heap building operation, BUILD-MAX-HEAP, and an operation to maintain the maximum heap, MAX-HEAPIFY. The detailed algorithm is as follows:

HEAPSORT(A) //n-1 calls to MAX-HEAPIFY, so, O(n*lgn)

 BUILD-MAX-HEAP(A) //Build *** heap, O(n)  
 for i ← length[A] downto 2
 do exchange A[1] <-> A[i]
      heap-size[A] ← heap-size[A] - 1
 MAX-HEAPIFY(A, 1) // Maintain the properties of the heap, O (lgn)  

As above, this is the complete description of the heap sort algorithm. Below, we will paste the two operations of building a heap and maintaining a heap in the above heap sort algorithm:

 BUILD-MAX-HEAP(A) //Build heap  
 heap-size[A] ← length[A]
 for i ← |_length[A]/2_| downto 1
 do MAX-HEAPIFY(A, i)
 MAX-HEAPIFY(A, i) //Keep the *** heap  
 l ← LEFT(i)
 r ← RIGHT(i)
 if l ≤ heap-size[A] and A[l] > A[i]
 then largest ← l
 else largest ← i
 if r ≤ heap-size[A] and A[r] > A[largest]
 then largest ← r
 if largest ≠ i
    then exchange A[i] <-> A[largest]
         MAX-HEAPIFY(A, largest)

The following is a demonstration of the heap sort algorithm (by constantly exchanging the top element with the last element, and then calling MAX-HEAPIFY to maintain the properties of the heap, one by one, from large to small, to clear all the elements in the heap, thus forming an ordered sequence. This is the entire process of heap sort.):

In the above figure, between a->b, b->c, ..., there is a process of calling MAX-HEAPIFY after the top largest element is exchanged with the smallest element. We know that the running time of this MAX-HEAPIFY is O(lgn), and to complete the entire heap sorting process, a total of O(n) such MAX-HEAPIFY operations are required. Therefore, the running time of the heap sorting algorithm is O(n*lgn).

Follow-up: Imagine a heap as a tree, a binary tree or something like that. Therefore, the time complexity of using a heap to search and delete data is O (logN). So what kind of binary tree is it? A special binary tree, divided into a heap and a minimum heap. A heap is big at the top and small at the bottom. A minimum heap is small at the top and big at the bottom.

Author: July