heap sort

definition

https://www.youtube.com/watch?v=j-DqQcNPGbE
http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/heap-delete.html

1. complete binary tree
2. parent node all larger/less than child
3. delete time 正比O(dep)== O(ln N)
   完滿二元樹深度LnN
4. sort每次log(N)做N次 => O(nlnN)

complete binary tree

increase node from top to bottom, left to right, no empty

property

for node idx(i)

• parent_node_idx = (i-1)/2
• left_child_idx= 2i+1
• right_child_idx= 2i+2

start from lowerest parent node with child: (length-1)/2

the following as max heap

    //delete/sort use
	public static void heapifyDown(int[] arr, int len, int process_idx) {

		if (process_idx >= len)
			return;

		int c1 = process_idx * 2 + 1;
		int c2 = process_idx * 2 + 2;

		int max_idx = process_idx;
		// find max value idx

		if (c1 < len && arr[max_idx] < arr[c1]) {// check left child node exist
			max_idx = c1;
		}

		if (c2 < len && arr[max_idx] < arr[c2]) {
			max_idx = c2;
		}

		if (max_idx != process_idx) {
			// swap
			swap(arr, max_idx, process_idx);
			heapifyDown(arr, len, max_idx);// process the modified child node
		}

	}

    // insert, insert at arr end,heapify up then do heat sort again
	public static void heapifyUp(int[] arr, int len, int process_idx) {

		if (process_idx >= len)
			return;

		int parent_idx = (process_idx - 1) / 2;

		int max_idx = parent_idx;
		// find max value idx

		if (arr[max_idx] < arr[process_idx]) {
			swap(arr, parent_idx, process_idx);
			heapifyUp(arr, len, parent_idx);// process the modified parents
		}

	}

	private static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

	public static void main(String[] args) {

		int[] t = new int[] { 2, 5, 3, 1, 10, 4 };

		int n = t.length;

		// heapify from the last parent node with child

		heap_sort(t, n);

		for (int num : t) {
			System.out.println(num);
		}

	}
    
    //do from bottom confirm the heap structure(non sort),make index 0 as min/max, build head不會進行同層比較
	private static void buildHeap(int[] arr, int n) {
		for (int i = (n - 1) / 2; i >= 0; i--) {
			heapifyDown(arr, n, i);
		}
	}

	private static void heap_sort(int[] arr, int n) {

		buildHeap(arr, n); // make index 0 as min or max

		for (int i = n - 1; i >= 0; i--) {
			swap(arr, i, 0); //the cur max/min place at i index
            
			heapifyDown(arr, i, 0); // heapify the processed node make the index 0 the cur max/min, the max/min one place at index n, we now sort until index n-1 to get the second one min/max then place at index n-1, until heap sort to index 0.
		}
	}


    //min heap,只維持heap特性 需跑heap sort才能排序
    private static int delete(int[] arr,int len,int k){
        //delete the indx k and replace the the last node, rebuild complete binary tree
        
        int r=arr[k];
        
        arr[k]=arr[len-1]; //last mv to delete hole
        int parent_idx = (k-1)/2;
        // why compare parent, heap of check parent-son, not check the sibling
    
        if(k==1 || arr[parent]<arr[k]){
            // parent smaller than son, min  heap correct, spray to lower level to check -> heapify down
            heapifyDown(arr,len-1,k); // if the parent smaller than the origin ar[n-1] then this resemble min heap(last one bigger), then heapify down to let the larger one down to bottom
        }else{
            heapifyUp(arr,len-1,k); // if the parent greater than the origin arr[n-1], the last one is smaller, should send to top for the min heap
        }
        
        return r;
        
    }