DS-Heap

Binary Heap

• Binary Heap
  • Heap
    • max-heap
    • min-heap
    • Heapsort
      • Basic operations
        • max-heapify
        • build-max-heap
        • heapsort
    • Priority queues
      • Basic operations
        • max-heap-insert
        • heap-extract-max
        • heap-increase-key
        • heap-maximum

Heap

The (binary) heap is an array object that we can view as a nearly complete binary tree. The tree is completely filled on all levels except possibly the lowest. It has two attributes: length and heap-size. Length gives the number of elements in the array, heap-size repensents how many elements in the heap are stored within the array. Only the elements in A[1,…, A.heap-size] where 1 <= A.heap-size <= A.length are valid elements of head. A[1] is the root.

public int parent(int i) {
    return i/2;
}

public int left(int i) {
    return 2i;
}

public int right(int i) {
    return 2i + 1;
}

max-heap

The max-heap property is that for every node i other than the root, A[Parent[i]] >= A[i].

min-heap

The min-heap property is that for every node i other than the root, A[Parent[i]] <= A[i].

Heapsort

Basic operations

max-heapify

//find the largest in left,right and i
//running time is O(lgn)
public void maxHeapify(int[] A, int i ) {
    int l = left(i);
    int r = right(i);
    int largest = 0;
    if (l<= A.heap_size && A[l] > A[i]) {
        largest = l;
    } else {
        largest = i;
    }

    if (r <= A.heap_size && A[r] > A[largest]) {
        largest = r;
    }

    if (largest != i) {
        exchange(A[i], A[largest]);
        maxHeapify(A, largest);
    }

}

build-max-heap

//running time is O(n)
public void buildMaxHeap(int[] A) {
    A.heap_size = A.length;
    for (int i = A.length/2; i >= 1; i--) {
        maxHeapify(A, i);
    }
}

heapsort

//running time is O(nlgn)
public void heapSort(int[] A) {
    buildMapHeap(A);
    for (int i = A.length; i > 1; i--) {
        exchange(A[i], A[1]);
        A.heap_size = A.heap_size - 1;
        maxHeapify(A, 1);
    }
}

Priority queues

Priority queues come in two forms: max-priority queues and min-priority queues. We can use max-priority queues to schedule jobs on a shared computer. A min-priority queue can be used in an event-driven simulator.

Basic operations

max-heap-insert

public void heapInsert(int[] A, int key) {
    A.heap_size = A.heap_size + 1;
    A[A.heap_size] = Integer.MIN_VALUE;
    heapIncreaseKey(A, A.heap_size, key);
}

heap-extract-max

public heapExtractMax(int[] A) {
    if (A.heap_size < 1) {
        throw RuntimeException("heap is empty!");
    }
    int max = A[1];
    A[1] = A[A.heap_size];//?
    A.heap_size = A.heap_size - 1;
    maxHeapify(A, 1);
    return max;
}

heap-increase-key

public void heapIncreaseKey(int[] A, int i, int key) {
    if (key < A[i]) {
        throw RuntimeException("");
    }
    A[i] = key;
    while (i > 1 && A[parent[i]] < A[i]) {
        exchange(A[i], A[parent[i]]);
        i = parent[i];
    }
}

heap-maximum

public int heapMax(int[] A) {
    return A[1];
}