What kind of sort is heap sort?

Heap sorting is a method of generating a maximum heap from an unordered sequence, exchanging the positions of the top element of the heap with the last element, and generating the remaining elements into a maximum heap. The elements are exchanged sequentially to generate a maximum heap. sorting.

Heap sort

Generate an unordered sequence into a maximum heap, and combine the top element of the heap with The last element swaps positions, and the remaining elements are generated to generate a maximum heap. The elements are exchanged in sequence and a maximum heap is generated.

Time complexity: O(NlogN) Space complexity: O(1)

Introduction:

Heap sort (English: Heapsort) refers to a sorting algorithm designed using the data structure of a heap. A heap is a structure that approximates a complete binary tree, and at the same time satisfies the heaping property: that is, the key value or index of a child node is always smaller (or larger) than its parent node.

Heap operation

In the heap data structure, the maximum value in the heap is always located at the root node (if the heap is used in a priority queue, the minimum value in the heap is located at the root node).

The following operations are defined in the heap:

Max Heapify: Adjust the end child node of the heap so that the child node is always smaller than the parent node

Create Max Heap (Build Max Heap): Reorder all data in the heap

HeapSort: Remove the root node of the first data and perform the recursive operation of the maximum heap adjustment

The above is the detailed content of What kind of sort is heap sort?. For more information, please follow other related articles on the PHP Chinese website!