Coding Life

在學習 Heap Sort 前要先了解資料結構中的二元樹

而 Heap Sort 會用到的是二元樹中的完美二元樹

先學會二元樹的走訪及排序方法才會有辨法了解程式是如何運作的

關於二元樹的說明請先參考其它網站

我有空才會再補上來

如果直接看程式碼不了解的話

建議依以下步驟學習Coding Heap Sort

1. 產生陣列後依左序走訪的方式印出所有值
2. 走訪過程中每個結點需檢查是否要與父結點交換值，如需交換，在交換完後需依序向上檢查至不需交換為止
3. 取值

這個 coding 的過程我就視情況看看要不要補上了

下面兩支程式 Main.java 只是產生陣列及顯示

Sort.java 才是 Heap Sort 的主體

Main.java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

public class Main {
  public static void main(String[] args) {
    List list = new ArrayList<>();
		
    for(int i=0; i<10; i++){
      list.add(new Random().nextInt(1000));
    }
		
    Comparator com = new Comparator() {
      public int compare(Integer num1, Integer num2) {
        return num1 - num2;
      }
    };
		
    new HeapSort().heapSort(list, com);
    System.out.println(list);
  }
}

Sort.java

import java.util.*;
  import static java.util.Collections.swap;

  public class Sort {    
    public <T> void heapSort(List<T> list, Comparator<? super T> com){
      List<T> sorted = new ArrayList<>();
      while(list.size() > 0){
        this.getBinaryTree(list, com);
        swap(list, 0, list.size()-1);
        sorted.add(list.get(list.size()-1));
        list.remove(list.size()-1);
      }
      list.addAll(sorted);
    }
    
    public <T> void getBinaryTree(List<T> list, Comparator<? super T> com){
      this.getBinaryTree(list, 1, com);
    }
    
    private <T> void getBinaryTree(List<T> list, int index, Comparator<? super T> com){
      for(int i=0; i<=1; i++){
        if(index*2+i <= list.size()){
          bubble(list, index*2+i, com);
          this.getBinaryTree(list, index*2+i, com);
        }
      }
    }
    
    private <T> void bubble(List<T> list, int index, Comparator<? super T> com){
      while(index > 1){
        if(com.compare(list.get(index-1), list.get(index/2-1)) < 0){
          swap(list, index-1, index/2-1);
          index /= 2;
        }else{
          break;
        }
    }
  }
}