Use bit shift to multiply or divide

// use bitwise shift to multiply or divide by 2
// shift to the left
public void multiply(int i) {
    return <<<i;
}
// shift to the right
public void divide(int i) {
    return >>>i;
}

def LEFT(i):
    return multiply(i)
def RIGHT(i):
    return multiply(i) + 1
def PARENT(i):
    return divide(i)

Heap Sort

def HEAPSORT(A):
    BUILD_MAX_HEAP(A);
    for i = A.length to 2:
        A[1], A[i] = A[i], A[1]
        A.heap_size = A.heap_size - 1
        MAX_HEAPIFY(A, 1)

The total time: \(O(n\lg{n})\)

Maintaining the heap property

LEFT (i) and RIGHT(i) are max-heap, but A[i] might be smaller than its children
Maintain the heap in max-heap property

def MAX_HEAPIFY(A, i):
    l = LEFT(i);
    r = RIGHT(i);
    largest = i
    # compare parent and two children
    if l <= A.heap_size and A[l] > A[i]:
        largest = l
    if r <= A.heap_size and A[r] > A[i]:
        largest = r
    # if parent is not the largest, exchange with the larger children
    if largest is not i:
        A[i], A[largest] = A[largest], A[i]
        # swap from top to bottom
        MAX_HEAPIFY(A, largest)

The worst case occurs when the bottom level of the tree is exactly half full

the children's subtrees each have size at most 2n/3

\[ T(n) \le T(2n/3)+\Theta(1) \]

\[ \therefore T(n) = O(h)\ while\ h\ = \lg n \]

Building a heap

def BUILD_MAX_HEAP(A):
    A.heap_size = A.length
    # iterate from the first node with child
    for i = PARENT(A.LENGTH) downto 1:
        MAX_HEAPIFY(A, i)

Analysis

The total time for BUILD_MAX_HEAPIFY:

\[ \sum ^{\lfloor \lg n\rfloor }_{h=0}\left\lceil \frac{n}{2^{h+1}}\right\rceil O( h) =O\left( n\sum ^{\lfloor \lg n\rfloor }_{h=0}\frac{h}{2^{h}}\right) \]

while

\[ \sum ^{\infty }_{h=0}\frac{h}{2^{h}} =\frac{1/2}{( 1-1/2)^{2}} =2 \]

Thus,

\[ O\left( n\sum ^{\lfloor \lg n\rfloor }_{h=0}\frac{h}{2^{h}}\right) =O\left( n\sum ^{\infty }_{h=0}\frac{h}{2^{h}}\right) =O( n) \]

Priority Queue

Priority Queue is a data structure implemented by heap.

Functions

Priority Queue supports following functions:

1537667998697

Application

Schedule jobs (processes) in the computer. When a process is finished or interrupted, the scheduler selects the highest-priority process by calling EXTRACT_MAX.

Implementation

We can use a heap to implement a priority queue.
We often need to store a handle to the corresponding application object in each heap element.
Here, the handle would typically be an array index.

def MAXIMUM (A):
    return A[1]

\(\Theta (1)\)

def EXTRACT_MAX (A):
    if A.heap_size < 1:
        raise Exception("heap underflow")
    max = A[1]
    A[1] = A[A.heap_size]
    A.heap_size -= 1
    MAX_HEAPIFY(A, 1)
    return max

\(O(\lg n)\)

def INCREASE_KEY (A, i, value):
    if value < A[i]:
        raise Exception("new key is smaller than current key")
    A[i] = value
    while i > 1 and A[PARENT(i)] < A[i]:
        A[PARENT(i)], A[i] = A[i], A[PARENT(i)]
        i = PARENT(i)

\(O(\lg n)\)

def INSERT (A, value):
    A.heap_size += 1
    A[A.heap_size] = float('-inf')
    HEAP_INCREASE_KEY(A, A.heap_size, value)

\(O(\lg n)\)

Conclusion

A heap can support any priority-queue operation on a set of size n in O(lg n) time.

algorithm