Basic Storage of Heap

I. Concept and Introduction

A heap is a special type of data structure in computer science.

A heap is typically an array that can be viewed as a complete binary tree.

Heaps satisfy the following properties:

• The value of a node in the heap is always less than or equal to, or greater than or equal to, the value of its parent node.
• A heap is always a complete binary tree.

II. Applicability

Heaps utilize the structure of a complete binary tree to maintain a set of data and perform related operations. The time complexity for a typical operation is between O(1) and O(logn). Heaps are commonly used for dynamic allocation and deallocation of objects in programs.

In scenarios involving priority queues, regular arrays or sorted arrays have a worst-case scenario of O(n^2), while heaps can improve the efficiency of enqueue and dequeue operations.

III. Structural Diagram

A binary heap is a complete binary tree where the value of each node is always less than or equal to the value of its parent node. The depth of this complete binary tree is k, and all levels (1 to k-1) except the k-th level have the maximum number of nodes. All nodes at the k-th level are consecutively located on the leftmost side.

The root node of the heap, which is the largest, is known as a max-heap, as shown below:

We can store a binary heap using an array, with the right-side numbers representing the array indices.

Assuming the current element's index position is i, we can derive the following rules:

parent(i) = i/2 (integer division)
left child(i) = 2*i
right child(i) = 2*i + 1

IV. Java Example Code

Source Code Download: Download

src/tutorialpro/heap/MaxHeap.java File Code:

package tutorialpro.heap;

/**
 * Heap definition
 */
public class MaxHeap<T> {
    private T[] data;
    private int count;
    // Constructor, creates an empty heap with capacity for 'capacity' elements
    public MaxHeap(int capacity){
        data = (T[])new Object[capacity+1];
        count = 0;
    }
    // Returns the number of elements in the heap
    public int size(){
        return count;
    }
    // Returns a boolean indicating whether the heap is empty
    public boolean isEmpty(){
        return count == 0;
    }
    // Test MaxHeap
    public static void main(String[] args) {
        MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
        System.out.println(maxHeap.size());
    }
}