iframe-proxy | Sunbelt Computer Software

121 lines (107 loc) · 3.16 KB

package Sorts;
import static Sorts.SortUtils.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 * Heap Sort Algorithm Implements MinHeap
 * @author Podshivalov Nikita (https://github.com/nikitap492)
public class HeapSort implements SortAlgorithm {
  private static class Heap<T extends Comparable<T>> {
    /** Array to store heap */
    private T[] heap;
     * Constructor
     * @param heap array of unordered integers
    public Heap(T[] heap) {
      this.heap = heap;
     * Heapifies subtree from top as root to last as last child
     * @param rootIndex index of root
     * @param lastChild index of last child
    private void heapSubtree(int rootIndex, int lastChild) {
      int leftIndex = rootIndex * 2 + 1;
      int rightIndex = rootIndex * 2 + 2;
      T root = heap[rootIndex];
      if (rightIndex <= lastChild) { // if has right and left children
        T left = heap[leftIndex];
        T right = heap[rightIndex];
        if (less(left, right) && less(left, root)) {
          swap(heap, leftIndex, rootIndex);
          heapSubtree(leftIndex, lastChild);
        } else if (less(right, root)) {
          swap(heap, rightIndex, rootIndex);
          heapSubtree(rightIndex, lastChild);
      } else if (leftIndex <= lastChild) { // if no right child, but has left child
        T left = heap[leftIndex];
        if (less(left, root)) {
          swap(heap, leftIndex, rootIndex);
          heapSubtree(leftIndex, lastChild);
     * Makes heap with root as root
     * @param root index of root of heap
    private void makeMinHeap(int root) {
      int leftIndex = root * 2 + 1;
      int rightIndex = root * 2 + 2;
      boolean hasLeftChild = leftIndex < heap.length;
      boolean hasRightChild = rightIndex < heap.length;
      if (hasRightChild) { // if has left and right
        makeMinHeap(leftIndex);
        makeMinHeap(rightIndex);
        heapSubtree(root, heap.length - 1);
      } else if (hasLeftChild) {
        heapSubtree(root, heap.length - 1);
     * Gets the root of heap
     * @return root of heap
    private T getRoot(int size) {
      swap(heap, 0, size);
      heapSubtree(0, size - 1);
      return heap[size]; // return old root
  @Override
  public <T extends Comparable<T>> T[] sort(T[] unsorted) {
    return sort(Arrays.asList(unsorted)).toArray(unsorted);
  @Override
  public <T extends Comparable<T>> List<T> sort(List<T> unsorted) {
    int size = unsorted.size();
    @SuppressWarnings("unchecked")
    Heap<T> heap = new Heap<>(unsorted.toArray((T[]) new Comparable[unsorted.size()]));
    heap.makeMinHeap(0); // make min heap using index 0 as root.
    List<T> sorted = new ArrayList<>(size);
    while (size > 0) {
      T min = heap.getRoot(--size);
      sorted.add(min);
    return sorted;
   * Main method
   * @param args the command line arguments
  public static void main(String[] args) {
    Integer[] heap = {4, 23, 6, 78, 1, 54, 231, 9, 12};
    HeapSort heapSort = new HeapSort();
    print(heapSort.sort(heap));

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

HeapSort.java

Latest commit

History

HeapSort.java

File metadata and controls