Status: not complete

Introduction

A heap is a tree-based data structure which

  1. satisfies the shape property: is an almost complete tree

  2. satisfies the heap property: in a max heap, for any given node C, if P is a parent of C, then the key of P is greated than or equal to the key of C.

The heap is one maximally efficient implementation of a priority queue.

Heap is partially ordered; there is no implied ordering between siblings or cousins and no implied sequence of an in-order traversal.

A heap is a useful data structure when it is necessary to repeatedly remove the object with the highest (or lowest) priority.

A binary heap is a heap that takes the form of a binary tree.

Validate a Heap

(1) Given an Array

Given an array of size n, check if it represent a binary max heap.

Implementation

An array will always satisfy the shape property of being a complete tree.

To check the heap property, we loop through the elements in the array and compare the value to that of its children. Notice that:

  1. Suppose the root node is at index 0 with last node at index n-1. Then for node at index i, its parent node(if it has any) is at index (i-1)/2, and its child nodes(if it has any) are at index 2i+1 and 2i+2.

  2. Suppose the root node is at index 1 with last node at index n. Then for node at index i, its parent node(if it has any) is at index i/2, and its child nodes (if it has any) are at index 2i and 2i+1.

  3. Suppose the root node is at index 0. Then all the nodes with indices greater than (n-2)/2 are leaf nodes. This is because $ 2(\frac{n-2}{2}) + 1 = n-1 $, which is already the index of the last element in the array.

  4. Suppose the root node is at index 0. It is possible that the node at index (n-2)/2 only has a left child.

One natural way is to loop through each elements in the array, treat it as the parent node and compare its value with that of its children’s.

bool isHeap(int arr[], int n){
    for(int i=0; i<=(n-2)/2; i++){
        if (arr[i] < arr[2*i+1])    // max heap
            return false;
        if (2*i+2 <= n-1 && arr[i] < arr[2*i+2])
            return false;
    }
    return true;
}

Another approach is to loop through each element other than the first one, treat it as a child node and compare it to its parent.

bool isHeap(int arr[], int n){
    if (n <= 1)
        return true;
    for (int i=1; i<=n-1; i++){     // i start at 1
        if (arr[i] > arr[(i-1)/2])
            return false;
    }
    return true;

(2) Given a Tree

Given a binary tree, check if it represents a binary max heap.

Implementation

I think this is correct.

bool isHeap(struct node* root){
    if (root == NULL)
        return true;
    if (root->left == NULL && root->right == NULL)
        return true;
    if (root->left == NULL && root->right != NULL)
        return false;
    if (root->left != NULL && root->right == NULL)
        return (root->val > root->left->val) &&
                isHeap(root->left);

    return (root->val > root->left->val) &&
            (root->val > root->right->val) &&
            isHeap(root->left) &&
            isHeap(root->right);
}

Insert

Let’s first define two operations of a max heap.

SiftUp: Swap a node that is too large with its parent until it is no larger than its parent.

SiftDown: Swap a node that is too small with its largest child until it is no smaller than either of its children.

  1. Add element to the end of the array
  2. Siftup that element.

Remove

  1. Remove root, and put the last element at root
  2. SiftDown the new root element.

Build a Heap

Lemma1: The number of internal nodes in a complete binary tree of $n$ nodes is $\lfloor n/2 \rfloor$.

Lemma2: A heap of size $n$ has at most $\lceil n/2^{h+1} \rceil$ nodes with height $h$.

Proof:

Prove by induction.

Base Case: for $h=0$, i.e. the leaf nodes, we can get it from lemma1:

\[n - \lfloor n/2 \rfloor = \lceil n/2 \rceil\]

Induction Step:

Method 1

Starting with an empty heap and insert each element into it.

Runtime: $O(nlogn)$

Method 2

Note that both SiftUp and SiftDown has a runtime proportional to the height of the heap. Additionally,