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[15];
    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[1];
        h[1] = 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;
            }
            /**
             * Up adjustment
             * */
            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[1] and h[n] exchange
3. Adjust h[1] 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[15];
    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[1];
            h[1] = 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;
            }
            /**
             * Up adjustment
             * */
            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