Zeta Oph's Study

[Data Structure (Java)] Heapsort 본문

프로그래밍/Java

[Data Structure (Java)] Heapsort

Zeta Oph 2024. 6. 3. 00:58

https://crane206265.tistory.com/85

 

[Data Structure (Java)] Heap

https://crane206265.tistory.com/84 [Data Structure (Java)] Tree (3) - Binary Search Treehttps://crane206265.tistory.com/82 [Data Structure (Java)] Tree (2) - Tree Traversal Algorithmshttps://crane206265.tistory.com/81 [Data Structure (Java)] Tree (1) -

crane206265.tistory.com

저번에 Heap을 공부했으니까, 이번엔 Heapsort를 공부해봅시다.


Heapsort Algorithm

1. heap construction : create a max-heap with all N keys
2. sortdown : repeatedly remove the maximum key

 

1. Heap Construction

Original array : Heap that violating heap-order

Every position in the array is the root of small subheap

--> Call sink() on all nodes make the subtree rooted at this node a heap

* Start scanning at halfway back through the array : Skip the subheaps of size 1

--> Finish calling sink() at the root (index 1)

==> The array restored to satisfy heap-order

// heap construction code
for(int k = N/2; k >= 1; k--) //N/2 : start scanning at halfway back
    sink(a, k, N) //a : target array & N : heap size

 

2. Sortdown

(1) Exchange the largest one with the last position in the array

(2) Remove the last one(the largest one) from the heap - (it is sorted : do not touch)

(3) Call sink() at the root : Restored heap to satisfy heap-order

(4) Repeat (1)~(3) until the heap becomes empty

==> All elements are sorted

while(N>1) {
    exch(a, 1, N--);
    sink(a, 1, N);
}

Running Time Analysis

1. sink-based heap construction : O(n)
<worst case>
at the root : exchange $h$ times
at the next level : $2(h-1)$ times <- (2 trees of height h-1)
at the next level : $4(h-1)$ times
...
at the bottom : no exchange

--> $\text{total exchange} = h+2(h-1)+4(h-2)+...$
$=2^{h+1}-h-2=(2^{h+1}-1)-h-1$
$=n-(h+1)<=n$
2. sortdown : O(n log n)
sink() -> exchange at most log n times
sink() for n keys

 

==> Heapsort : In-place sorthing algorithm with O(n log n)

* In-place : Instead of transferring elements out of the sequence and then back in, we simply rearrange them

--> useful at tight memory


Heapsort Implementation

Heapsort Implementation as method in Heap class (for String)

import java.lang.Comparable;

public class Heap {
    //This class cannot be instantiated : just for sorting
    private Heap() {}

	//----- Heapsort -----
    @SuppressWarnings("rawtypes")
    public static void sort(Comparable[] pq) {
        int n = pq.length;
        for(int k = n/2; k >= 1; k--) {
            sink(pq, k, n);
        }
        while(n > 1) {
            exch(pq, 1, n--);
            sink(pq, 1, n);
        }
    }
    
    
    //----- helper methods -----
    @SuppressWarnings("rawtypes")
    private static void sink(Comparable[] pq, int k, int n) {
        while(2*k <= n) {
            int j = 2*k;
            if(j < n && less(pq, j, j+1)) j++;
            if(!less(pq, k, j)) break;
            exch(pq, k, j);
            k = j;
        }
    }
	
    //Heap is 1-based indexing, but given array starts at index 0
    //==> implement less(), exch() method with considering this
    @SuppressWarnings({ "rawtypes", "unchecked" })
    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i-1].compareTo(pq[j-1]) < 0;
    }

    private static void exch(Object[] pq, int i, int j) {
        Object temp = pq[i-1];
        pq[i-1] = pq[j-1];
        pq[j-1] = temp;
    }
}