Heap sorting (java implementation)

I. Preface

A heap is an array that can be seen as an approximate complete binary tree. The array representing the heap includes two attributes: A.length the number of array elements, and A.heapSize the number of elements in the array. The relationship here is:

 0<= A.heapSize<=A.length

The root node of the tree is A[1], and the time complexity of heap sorting is O(nlgn). Binary heap can be divided into two types: maximum heap and minimum heap. The maximum heap is parent > = child. The smallest heap is the opposite. Next, use java to realize the maximum heap, mainly refer to the introduction of algorithm.

2, Maximum heap implementation

Since the array does not have heapSize, you need to deal with it yourself.

public class HeapSort {

    public static void main(String[] args) {
        HeapSort hs = new HeapSort();
        // The - 1 here is not an element in the heap, just let the array count from 1
        int a[] = { -1, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
        int heapSize = a.length - 1;
        hs.build_max_heap(a);
        hs.heapSort(a);
        hs.heapExtractMax(a, heapSize);
        hs.print(a);
    }

    /**
     * Take out the maximum value
     */
    public int heapMaximum(int[] a) {
        return a[1];
    }

    /**
     * Takes the value of the largest element and takes it from the array
     */
    public int heapExtractMax(int a[], int heapSize) {
        if (heapSize < 1) {
            throw new RuntimeException("heap underflow");
        }
        int max = a[1];
        a[1] = a[heapSize];
        heapSize = heapSize - 1;
        max_heapify(a, 1, heapSize);
        return max;
    }

    /**
     * Increase the value of a node
     */
    public void heapIncreaseKey(int[] a, int i, int key) {
        if (key < a[i]) {
            throw new RuntimeException("new key is smaller than current key");
        }
        a[i] = key;
        while (i > 1 && a[parent(i)] < a[i]) {
            swap(a, i, parent(i));
            i = parent(i);
        }

    }

    /**
     * Insertion element
     */
    public void maxHeapInsert(int[] a, int key, int heapSize) {
        heapSize = heapSize + 1;
        a[heapSize] = 0;
        heapIncreaseKey(a, heapSize, key);
    }

    /**
     * Heap sort
     */
    public void heapSort(int a[]) {
        build_max_heap(a);
        int len = a.length - 1;
        for (int i = len; i >= 2; i--) {
            swap(a, 1, i);
            len = len - 1;
            max_heapify(a, 1, len);
        }

        print(a);
    }

    /**
     * Build maximum heap
     */
    public void build_max_heap(int[] a) {
        int i = a.length / 2;
        int heap_size = a.length - 1;
        for (; i >= 1; i--) {
            max_heapify(a, i, heap_size);
        }
    }

    /**
     * For tree height h, time complexity O(h)
     */
    public void max_heapify(int[] a, int i, int heap_size) {
        int l = left(i);
        int r = right(i);
        int largest;
        if (l <= heap_size && a[l] > a[i]) {
            largest = l;
        } else {
            largest = i;
        }

        if (r <= heap_size && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, largest, i);
            max_heapify(a, largest, heap_size);
        }
    }
    /**
     *  Parent node
     */
    public int parent(int i) {
        return i / 2;
    }
    /**
     *  Left child
     */
    public int left(int i) {
        return 2 * i;
    }
    /**
     *  Right child
     */
    public int right(int i) {
        return 2 * i + 1;
    }
    /**
     *  Exchange the values of two elements in an array
     */
    public void swap(int a[], int x, int y) {
        try {
            int t = a[x];
            a[x] = a[y];
            a[y] = t;
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("x:" + x + ";y:" + y);
        }
    }

    /**
     * Printing
     */
    public void print(int[] a) {
        for (int i : a) {
            System.out.println("a=>" + i);
        }
    }

}

Three, summary

In general, heap sorting is very simple, and what has been written in the introduction of algorithm is very clear. I bought this book when I was a junior. I didn't read it very much at that time. Now I want to read it again. It's a classic after all. I hope I can keep reading it. Internal skill strengthening~~~~~

Reference: introduction to algorithm

Tags: Java

Posted on Sun, 05 Apr 2020 13:06:38 -0700 by Darkness31