Shulou(Shulou.com)06/01 Report--

This article shares with you the content of a sample analysis of heap sorting in web. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Heap sorting is a sort algorithm designed by using the data structure of heap. Heap sorting is a sort of * * selection sort. * * its worst, best and average time complexity is O (nlogn), and it is also unstable.

Heap sorting can be said to be a selective sort that uses the concept of heap to sort. There are two methods:

Large top heap: the value of each node is greater than or equal to the value of its child nodes, used in ascending order in the heap sorting algorithm; small top heap: the value of each node is less than or equal to the value of its child nodes, used in descending order in the heap sort algorithm

The average time complexity of heap sorting is nlogn.

1. The algorithm step is to create a heap H [0... Exchange the head (maximum) and tail of the heap; reduce the size of the heap by 1 and call shift_down (0) to adjust the data at the top of the new array to the appropriate position; repeat step 2 until the size of the heap is 1. two。 Moving picture demonstration

Code implementation

JavaScript

Example

Var len; / / because multiple declared functions require data length, set len to the global variable function buildMaxHeap (arr) {/ / establish a large top heap len = arr.length; for (var I = Math.floor (len/2); I > = 0; Imam -) {heapify (arr, I) }} function heapify (arr, I) {/ / heap adjustment var left = 2 * I + 1, right = 2 * I + 2, largest = I; if (left arr [largest]) {largest = left;} if (right arr [largest]) {largest = right;} if (largest! = I) {swap (arr, I, largest); heapify (arr, largest) }} function swap (arr, I, j) {var temp = arr [I]; arr [I] = arr [j]; arr [j] = temp;} function heapSort (arr) {buildMaxHeap (arr); for (var I = arr.length-1; I > 0; iMuk -) {swap (arr, 0, I); len--; heapify (arr, 0);} return arr;}

Python

Example

Def buildMaxHeap (arr): import math for i in range (math.floor (len (arr) / 2),-1) heapify (arr,i) def heapify (arr,i): left = 2*i+1 right = 2*i+2 largest = i if left arr [largest]: largest = left if right arr [largest]: largest = right if largest! = I: swap (arr,i, largest) heapify (arr, largest) def swap (arr,i J): arr [I], arr [j] = arr [j], arr [I] def heapSort (arr): global arrLen arrLen = len (arr) buildMaxHeap (arr) for i in range (len (arr)-1): swap (arr,0,i) arrLen-= 1 heapify (arr,0) return arr

Go

Example

Func heapSort (arr [] int) [] int {arrLen: = len (arr) buildMaxHeap (arr, arrLen) for I: = arrLen-1; I > = 0; imuri-{swap (arr, 0, I) arrLen-= 1 heapify (arr, 0, arrLen)} return arr} func buildMaxHeap (arr [] int, arrLen int) {for I: = arrLen / 2; I > = 0 I heapify-{heapify (arr, I, arrLen)}} func heapify (arr [] int, I ArrLen int) {left: = 2cubi + 1 right: = 2pragi + 2 largest: = i if left arr [largest] {largest = left} if right arr [largest] {largest = right} if largest! = I {swap (arr, I, largest) heapify (arr, largest) ArrLen)} func swap (arr [] int, I, j int) {arr [I], arr [j] = arr [j], arr [I]}

Java

Example

Public class HeapSort implements IArraySort {@ Override public int [] sort (int [] sourceArray) throws Exception {/ / A copy of arr without changing the parameter contents int [] arr = Arrays.copyOf (sourceArray, sourceArray.length); int len = arr.length; buildMaxHeap (arr, len); for (int I = len- 1; I > 0; iMuc -) {swap (arr, 0, I); len-- Heapify (arr, 0, len);} return arr;} private void buildMaxHeap (int [] arr, int len) {for (int I = (int) Math.floor (len / 2); I > = 0; iMui -) {heapify (arr, I, len);}} private void heapify (int [] arr, int I, int len) {int left = 2 * I + 1 Int right = 2 * I + 2; int largest = I; if (left arr [largest]) {largest = left;} if (right arr [largest]) {largest = right;} if (largest! = I) {swap (arr, I, largest); heapify (arr, largest, len) }} private void swap (int [] arr, int I, int j) {int temp = arr [I]; arr [I] = arr [j]; arr [j] = temp;}}

PHP

Example

Function buildMaxHeap (& $arr) {global $len; for ($I = floor ($len/2); $I > = 0; $I -) {heapify ($arr, $I);}} function heapify (& $arr, $I) {global $len; $left = 2 * $I + 1; $right = 2 * $I + 2; $largest = $I; if ($left $len & $arr [$left] > $arr [$largest]) {$largest = $left } if ($right $len & & $arr [$right] > $arr [$largest]) {$largest = $right;} if ($largest! = $I) {swap ($arr, $I, $largest); heapify ($arr, $largest);} function swap (& $arr, $I, $j) {$temp = $arr [$I]; $arr [$I] = $arr [$j]; $arr [$j] = $temp;} function heapSort ($arr) {global $len; $len = count ($arr); buildMaxHeap ($arr) For ($I = count ($arr)-1; $I > 0; $iMel -) {swap ($arr, 0, $I); $len--; heapify ($arr, 0);} return $arr;}

C

Example

# include#includevoid swap (int * a, int * b) {int temp = * b; * b = * a; * a = temp;} void max_heapify (int arr [], int start, int end) {/ / create parent node and child node int dad = start; int son = dad * 2 + 1 While (son if (son + 1 if (arr [dad] > arr [son]) / / if the parent node is greater than the child node to represent the completion, jump directly out of the function return; else {/ / otherwise the parent and son content will be compared to the swap (& Arrdad, & Arrson]; dad = son; son = dad * 2 + 1 } void heap_sort (int arr [], int len) {int I; / initialize, I integrate the for from the last parent (I = len / 2-1; I > = 0; I len -) max_heapify (arr, I, len-1); / / first crosses the first element with the first arranged element, and then re-arranges until the for is finished (I = len-1) I > 0; iMurray -) {swap (& arr [0], & arr [I]); max_heapify (arr, 0, i1);}} int main () {int arr [] = {3, 5, 3, 0, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 2, 5, 9, 7, 4, 0, 2, 6}. Int len = (int) sizeof (arr) / sizeof (* arr); heap_sort (arr, len); int i; for (I = 0; I printf ("% d", arr [I]); printf ("\ n"); return 0;}

C++

Example # include#includeusing namespace std;void max_heapify (int arr [], int start, int end) {/ / create parent node and child node pointer int dad = start; int son = dad * 2 + 1; while (son if (son + 1 if (arr [dad] > arr [son]) / / if the parent node is larger than the child node for completion, jump out of the function return directly Else {/ / otherwise, the parent-son content re-update the node and point comparison swap (arr [dad], arr [son]); dad = son; son = dad * 2 + 1;}} void heap_sort (int arr [], int len) {/ / initialization, I start the for from the last parent (int I = len / 2-1; I > = 0 IMel -) max_heapify (arr, I, len-1); / / first crosses the first element with the one that has already been arranged, and then rearranges it (the element before the newly adjusted element) to for (int I = len-1; I > 0; iMuk -) {swap (arr [0], arr [I]); max_heapify (arr, 0, i1) } int main () {int arr [] = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6}; int len = (int) sizeof (arr) / sizeof (* arr); heap_sort (arr, len); for (int I = 0; I'; cout return 0) } Thank you for reading! This is the end of this article on "sample analysis of heap sorting in web". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it for more people to see!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.