# Sorting algorithm -- heap sorting (JAVA)

A very important application of heap is heap sorting. Like fast sorting, the time complexity of heap sorting is O(NlgN)
The first idea of heap sorting is as follows:
1. Create a small root heap
2. Delete the top element every time and output the top element (there is a process of adjustment in the deleted function, each adjustment)
Time complexity: O(N · logN)

Input:
14
99 5 36 2 19 1 46 12 7 22 25 28 17 92

Output:
1 2 5 7 12 17 19 22 25 28 36 46 92 99

```import java.util.Scanner;

public class Main {
static int num, n = 0;
static int[] h = new int;
static Scanner input = new Scanner(System.in);
public static void main(String[] args) {
num = input.nextInt();
for (int i = 1; i <= num; i++) {
h[i] = input.nextInt();
}
n = num;

create();

for (int i = 1; i <= num; i++) {
System.out.print(deletemax() + " ");
}
}

private static void create() {
/**
* Downward adjustment from the last non leaf node to the first node
* */
for (int i = n / 2; i >= 1; i--) {
siftdown(i);
}
}

private static int deletemax() {
int temp = h;
h = h[n];
n--;
siftdown(1);
return temp;
}

private static void siftup(int i) {
int flag = 0;
/**
* Pile top
* */
if (i == 1) {
return;
}
while (i != 1 && flag == 0) {
/**
* Whether the current node is smaller than the parent node
* */
if (h[i] < h[i/2]) {
int temp = h[i];
h[i] = h[i/2];
h[i/2] = temp;
} else {
flag = 1;
}
/**
* */
i = i/2;

}
}

private static void siftdown(int i) {
int t, flag = 0;
while (i * 2 <= n && flag == 0) {
if (h[i] > h[i*2]) {
t = i * 2;
} else {
t = i;
}
if (i * 2 + 1 <= n) {
if (h[t] > h[i * 2 + 1]) {
t = i * 2 + 1;
}
}
if (t != i) {
int temp = h[t];
h[t] = h[i];
h[i] = temp;
i = t;
} else {
flag = 1;
}
}
}
}
```

The second idea of heap sorting is as follows:
1. Create a large root heap
2.h and h[n] exchange
3. Adjust h downward, n –
Time complexity: O(N · logN)

Input:
14
99 5 36 2 19 1 46 12 7 22 25 28 17 92

Output:
1 2 5 7 12 17 19 22 25 28 36 46 92 99

```import java.util.Scanner;

public class Main {
static int num, n = 0;
static int[] h = new int;
static Scanner input = new Scanner(System.in);
public static void main(String[] args) {
num = input.nextInt();
for (int i = 1; i <= num; i++) {
h[i] = input.nextInt();
}
n = num;

create();

heapsort();
for (int i = 1; i <= num; i++) {
System.out.print(h[i] + " ");
}
}

private static void heapsort() {
while (n > 1) {
int temp = h[n];
h[n] = h;
h = temp;
n--;
siftdown(1);
}
}

private static void create() {
/**
* Upward adjustment from the last non leaf node to the first node
* */
for (int i = n / 2; i >= 1; i--) {
siftdown(i);
}
}

private static void siftup(int i) {
int flag = 0;
/**
* Pile top
* */
if (i == 1) {
return;
}
while (i != 1 && flag == 0) {
/**
* Whether the current node is smaller than the parent node
* */
if (h[i] > h[i/2]) {
int temp = h[i];
h[i] = h[i/2];
h[i/2] = temp;
} else {
flag = 1;
}
/**
* */
i = i/2;

}
}

private static void siftdown(int i) {
int t, flag = 0;
while (i * 2 <= n && flag == 0) {
if (h[i] < h[i*2]) {
t = i * 2;
} else {
t = i;
}
if (i * 2 + 1 <= n) {
if (h[t] < h[i * 2 + 1]) {
t = i * 2 + 1;
}
}
if (t != i) {
int temp = h[t];
h[t] = h[i];
h[i] = temp;
i = t;
} else {
flag = 1;
}
}
}
}
```

Heap is a data structure of priority queue
For ordinary queues, it is more convenient to insert, but the time complexity is higher to find the largest (or smallest) element in the queue;
For sorted arrays, finding the largest (or smallest) element is not a problem, but inserting an element requires the later element to move backward as a whole, and the time complexity is still very high.
The priority queue structure can well solve the above two operations.
The previous Dijkstra algorithm can be optimized by heap.

Tags: Java

Posted on Sat, 02 May 2020 10:35:29 -0700 by flashpipe