“This is the 13th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge.”

Follow me for more updates

Data structure and algorithm (I): time complexity and space complexity

Data structure and algorithm (2): stack

Data structure and algorithm (3): queue

Data structure and algorithm (4): single linked list

Data structure and algorithm (5): two-way linked list

Data structure and algorithm (6): hash table

Data Structures and algorithms (7): trees

Data Structure and algorithm (8): sorting algorithm

Data Structures and algorithms (9): classical algorithm interview questions

preface

Before introducing heap sorting, let’s briefly review full binary trees and heaps

  • Complete binomial tree: a binomial tree is called a complete binomial tree if the last node of the last layer is full, and the nodes of the last layer are distributed from left to right.

  • Heap is a complete binary tree which is stored sequentially. The storage of heap is generally realized by array

    • Large top heap: the value of each node is greater than or equal to the value of its left and right children

    • Small top heap: the value of each node is less than or equal to the value of its left and right children

For details on full binary trees and heaps, see Data Structures and Algorithms (7): Trees, which will be updated tomorrow

Heap sort Idea

Heap sort is an optional sort that can store the heap sequentially in a one-dimensional array. So how do you sort with the heap? With ascending order, the first to collating sequence according to the order from top to bottom, from left to right to build into a large heap, so the top of the heap root node is the greatest element, taking out a root node, then the rest of the elements and structure into a new pile (how to ensure maximum take more efficient to build a new reactor, is the root node arr [0] and the last leaf node ar R [n – 1) to carry on the exchange, and then take away the last leaf node arr [n – 1), the heap does not meet the conditions of the pile top, can only say that it is a complete binary tree, so it should be adjusted recursive fully binary tree to make it become a big heap), also meet the root node is the largest element, and remove the root node at this time, continue to build a new heap, execution cycles.

For example, to sort the array {100,33,3,7,11,6,8,5} in ascending order:

Step 1: Build a complete binary tree

First build a full binary tree from the array, as shown below

(There is no need to do this in this code, because a full binary tree can be stored as a one-dimensional array, and the initial array is a full binary tree by default.)

Step 2: Build the full binary tree into a large top heap

We start with the last parent node, which is 7 with the subscript 3. Since 7 is the parent node, it is larger than its child node 5, so we don’t have to adjust it. Let’s look at 3 with subscript 2, because 3 is less than the child node, let’s swap the largest child node 8 with 3; And then look at 33 of index 1, which is larger than the two children, so you don’t have to switch; If you look at 100 at zero, it’s bigger than the child node, so you don’t switch; At this point the large top heap is built. As is shown in

Note here: If you want to construct a full heap, Construct it up from below, and after every time of clearing, are recursive maintenance to “exchange of the child node to the parent node of the heap, because if the switching node is very small, so may be less than the heap below it, so you will return to the maintenance, recursive maintenance function of the pile in the code is heapify method (behind the heapify method will post code) In heapify, if the parent node is smaller than a child node in the recursion process, then switch positions and continue recursively maintaining the heap from the position of the child node being exchanged. If the parent is bigger than both of the children, you don’t need to swap, but of course the parent is bigger than the heap below the child, so you don’t need to recurse the heap below the child

Step 3: Take out the maximum and adjust it to the new heap. The top element of the big top heap is the maximum, swap it with the last element, and remove the last element from the heap, which is the maximum, as shown in the figure below

Has not satisfied the characteristics of the heap at this moment, can only say that it is a complete binary tree, so at this time to adjust, pay attention to adjust the heap heap and create order, adjustment of should begin from the root node, parent and child nodes exchange, after the next recursive adjustment after a child of the pile is in exchange for the child to the parent node of the heap, this step, for example, from the subscript 5 to 0 33, 5, and exchange, after the next recursive subscript 1 5 can be adjusted to the parent node of pile, because 5 is greater than its right child 11, so swap places (note 5 after the exchange, 33 and 8 as a child of a parent with a subscript 2 don’t need a recursive adjustment, because after the exchange, with eight heap for parent child did not move, still meet the characteristics of pile)

Now that it has been adjusted to become the new heap, the top element is swapped with the last element, namely 33 and 3, and 33 is removed, as shown in the figure

By analogy, the middle adjustment process is omitted, and the last adjustment is completed as shown in the figure

Arr [0] and arr[n-i] are exchanged each time. For example, the first swap is arr[0] and arr[n-1], and the second swap is arr[0] and arr[n-1] Arr [n-2], and so on. After the last adjustment, the elements of the array are sorted in ascending order.

Pay attention to

If you want to construct a full heap, you also need to call the heapify method to recursively maintain the heap below. However, it is important to note that you do not need to recursively maintain the heap sorting here, because you only need to make sure that the top element of the heap is the largest. You do not need to maintain a full heap.

Heap sort complete code

//8 heapSort -(void)heapSort:(NSMutableArray*)arr{//1. [self buildHeap:arr]; int n = (int)arr.count; For (int I = n-1; int I = n-1; i>=0; i--) { [self swapArray:arr index1:0 index2:i]; [self heapify:arr parent:0 n: I]; / / the number of heap gradually reduce 1 next time, because the maximum comes out, will be away from the heap}} / * * 1, according to node I, the two child nodes, the three nodes constitute a minimum unit of complete binary tree (ignore) cross 2, find the smallest unit of a maximum of full binary tree, And switch it to the position 3 of the parent node, recursively call, maintain the heap relationship between the child node and the child node destroyed after the switch, */ -(void)heapify:(NSMutableArray*)arr parent:(int) I n:(int)n{int c1 = I *2+1; Int c2 = I *2+2; Int Max = I; Max if (c1 < n && [arr[c1] intValue] > [arr[Max] intValue]) {Max = c1; } if (c2 < n && [arr[c2] intValue] > [arr[max] intValue]) { max = c2; } //max ! = I, that is, the maximum value is not the original parent node, so you need to swap positions, but after the swap, the new element to be swapped may be smaller than the heap below, so you need to recursively maintain the heap down if (Max! = i) { [self swapArray:arr index1:max index2:i]; [self heapify:arr parent:max n:n]; } } -(void)buildHeap:(NSMutableArray*)arr{ int n = (int)arr.count; Last_node int last_node = n-1; // The subscript of the complete binary tree corresponds to the subscript of the array one to one. P = ((last_node-1)/2) int parent = (last_node-1)/2; for (int i = parent; i>=0; i--) { [self heapify:arr parent:i n:n]; }}Copy the code

Performance of heap sort

The best, best, and average time complexity of heapsort is O(nlogn), and the space complexity is O(1). It is an unstable sort

Other sorting algorithms

Sorting algorithm :1) Direct insertion sort

Sorting algorithm :2) Hill sort

Sorting algorithm :3) Bubble sort

Sorting algorithm :4) quick sort

Sorting algorithm :5) select sorting

Sorting algorithm :6) merge sort

Sorting algorithm :7) radix sort

Sorting algorithm :8) heap sort