java heap sorting principle and algorithm implementation

From the introduction of heap sort to the algorithm implementation of heap sort, it is as follows:

1. Introduction

Heap sort is built on the heap 数据结构 Based on the selection sort, is the address sort, time complexity O(nlogn), heap sort is not a stable sort. The heap commonly used in heap sort is the largest heap.

2. Definition of heap

A heap is a data structure, a special complete tree, usually divided into the largest heap and the smallest heap. The maximum heap is defined as the largest root node, and the subtrees around the root node are the maximum heap. Similarly, the minimum heap is defined as the minimum of the root node, and both the left and right subtrees of the root node are minimum heaps.

The maximum heap satisfies that every parent is greater than its left and right children, while the minimum heap satisfies that every parent is less than its right and left children.

3. The heap sort

3.1 Heap storage

In heap sort, the two-tree represented by heap does not need to be stored in the computer in the way of pointer, only need to use array, the nodes of the tree, from top to bottom, from left to right 1 each into the array.

Therefore, if the initial index of an array is 0, for 1 node i, its parent index is ⌊ i / 2 & # 8971; , its left child index is 2i+1, and its right child index is 2i+2. The last non-leaf node is the father of the last node. If the array length is n, the index is ⌊ (n - 1) / 2 & # 8971; .

3.2 Main steps of heap sort

Build an unordered sequence into the largest heap

The array is divided into two regions, the ordered region and the unordered region. An integer i is initially created as the length of the array to divide the ordered region and the unordered region. The ordered region is initially empty.

Swap the top element with the last unordered element, then i-1.

Adjusts so that all elements of an unordered region are regrouped to their maximum size.

Repeat steps 3 and 4 until i = 0

3.3 Heap adjustment

Suppose that there is a complete 2-branched tree, and both its left and right subtrees are the largest heap, how to adjust the 2-branched tree to become the largest heap? If the root is greater than the left and the right, then it's already the largest, so you don't have to adjust. Otherwise, swap the root and the larger of the left and right children. Assuming that the left node is swapped, the right subtree is still the largest, the left subtree is not fixed, but the left and right subtrees of the left subtree are still the largest, so keep recursing and adjust.

Therefore, the adjustment step after exchanging the last element and the top element is the same as the 1 mentioned above. You can also use this point to build the largest heap out of an unordered sequence. From the last non-leaf node to the first non-leaf node (root node), the adjustment described above can be called once in order for these nodes to be the subtrees of the root node (the left and right subtrees of this subtree must be the largest heap each time).

4. Algorithm implementation

#include <stdio.h>
void swap(int *a,int *b) {
 int temp = *a;
 *a = *b;
 *b = temp;
}
// The left and right subtrees are the largest, and the top and the bottom are adjusted to be the largest , root_index Is the root node of the tree to be adjusted, length Is the length of the unordered region 
void adjust(int array[],int root_index,int length) {
 int left_child = root_index*2+1;
 int right_child = left_child+1;
 int left_or_right = 0;
 if((left_child >= length && right_child >= length) || (left_child >= length && array[root_index] >= array[right_child]) ||
 (right_child >= length && array[root_index] >= array[left_child]) || (array[root_index] >= array[left_child] && array[root_index] >= array[right_child])){
  return;
 }
 else if (array[left_child] >= array[root_index] && (right_child >= length || array[left_child] >= array[right_child])) {
  left_or_right = 1;
 }
 else if (array[right_child] >= array[root_index] && (left_child >= length || array[right_child] >= array[left_child])) {
  left_or_right = 0;
 }
 if(left_or_right) {
  swap(&array[left_child],&array[root_index]);
  adjust(array,left_child,length);
 }
 else {
  swap(&array[right_child],&array[root_index]);
  adjust(array,right_child,length);  
 }
}
//heapsort Master recursion, each 1 The secondary will be unordered at the end 1 The top element is swapped with the top element, and the top element is added to the ordered region, so the ordered region is added 1, Disordered area reduction 1 The unordered region is left 1 The recursion ends at the number of elements 
void heapsort_main(int array[],int length,int last_index) {
 int i;
 if(last_index == 0)
  return;
 swap(&array[0],&array[last_index]);
 adjust(array,0,last_index);
 heapsort_main(array,length,last_index-1);
} 
// The entry function, array It's the array to sort, length Its length is 
void heapsort(int array[],int length) {
 int i;
 for(i = length/2-1;i >= 0;i--) {
  adjust(array,i,length);
 }
 heapsort_main(array,length,length-1);
}
int main(int argc,char *argv[]) {
 int array[9] = {1,1,1,2,3,5,2,3,5};
 heapsort(array,9);
 int i;
 for(i = 0;i < 9;i++) {
  printf("%d ",array[i]);
 }
}

5. Heap sort nature

Time complexity O(nlogn)

Space complexity O(1)

Unstable sort

This article sort the contents of the heap, hoping to help the friends in need