IDEA plug-ins commonly used by programmers: github.com/silently952…

Fully open source Taoke project: github.com/silently952…

Wechat official account: Beta learning Java

preface

In the previous article, we used binary heap to implement the priority queue. If we continuously call remove minimum (or maximum) from the constructed priority queue and output the result to another array, then we can sort all the elements of the array. This is the heap sort we need to learn. Before we look at this, we need to look at the previous article, “How Easy it is to implement priority queues.”

The heap sort process has two main stages:

  • Construct raw data into an ordered heap (construct heap)
  • Fetching all elements from the heap in descending order yields the sort result (sinking sort)

To begin, we need to modify the sink() method from the previous article;

Make sure that we use the original array directly when sorting, without wasting space by creating a secondary array. Since we need to reduce the heap size dynamically, we need to pass size as a parameter;

Secondly, the index of our array starts from 0, which is a little different from the previous priority order. For the left node of k, the index is 2k+1, and the right index is 2K +2

private void sink(Comparable[] queue, int k, int size) { while (2 * k + 1 < size) { int i = 2 * k + 1; if (i < size - 1 && less(queue[i], queue[i + 1])) { i++; } if (less(queue[i], queue[k])) { break; } exch(queue, i, k); k = i; }}Copy the code

Constructing heap

To construct an input number into a heap order, we have two ways:

  1. Iterate through the array from left to right and float swim() to ensure that the elements to the left of the pointer are heap-ordered, just as they were inserted into the priority queue
  2. Since each position in the array is already a node of the heap, we can construct the heap by calling the sink() operation from right to left. We can skip the elements whose subheap is 1, so we only need to scan half of the array. It’s much more efficient.

For example, enter array a[]={8,3,6,1,4,7,2}

Sinking sorting

Sink is the second stage of heap sorting, where we remove the largest element and place it in the empty space of the array after the heap has shrunk. When all the elements have been processed, the entire array will be in order

Sinking sort demonstration process (figure not completely drawn) :

Heap sort code implementation

@Override public void sort(Comparable[] array) { int size = array.length; for (int k = size / 2; k >= 0; k--) { sink(array, k, size); } while (size > 0) { exch(array, 0, --size); sink(array, 0, size); }}Copy the code

All source code has been put into github repository github.com/silently952…

Finally (pay attention, don’t get lost)

There may be more or less deficiencies and mistakes in the article, suggestions or opinions are welcome to comment and exchange.

Finally, writing is not easy, please do not white whoring I yo, I hope friends can point comment attention to three even, because these are all the power source I share 🙏