dsa midterm #2

Heap Data Structure

A binary tree in which every node is larger than the values associated with either child. This means the largest or smallest value is always at the top (root) of the tree.

Complete Binary Tree (Shape Property)

A heap is always a complete binary tree wherein all levels are filled except possibly the last, which is filled from left to right without skipping nodes. This allows representation using arrays (index-based), reducing pointer overhead.

Heap Order Property

The heap must satisfy the heap order property, which differs for max-heaps and min-heaps. These are the two (2) types of heap data structure.

Max-Heap

In a max-heap, the parent node is always greater than or equal to its children. This ensures that the largest value is always at the root of the tree.

Min-Heap

In a min-heap, the parent node is always less than or equal to its children. This ensures that the smallest value is always at the root of the tree.

Heap Operations

These are the core operations used to manage a heap, whether it is a min-heap or max-heap.

Insert (Push)

Adds a new element to the heap by adding it at the bottom.

Extract Root (Pop)

Removes and returns the root element, replacing it with the last element.

Peek (Get Root)

Returns the root without removing it.

Replace

Removes the root and inserts a new element in a single operation.

Heapify

The process of converting an arbitrary array (no specific structure or order) into a valid heap. It ensures the heap property (parent ≥ or ≤ children) is maintained from a given node down to its descendants.

Up-Heapify (Bubble-Up)

Used after inserting a new element to restore the heap property by moving the element up the tree.

Down-Heapify (Bubble-Down)

Used after deleting the root element to restore the heap property by moving the new root element down the tree.

Priority Queue

A priority queue is an abstract data type that operates like a regular queue, except that each element has a priority level, and elements are dequeued based on their priority, not just their arrival order.

Difference from Regular Queue

Unlike regular queues that process elements in first-in, first-out (FIFO) manner, priority queues ensure that elements with higher priority are processed first.

Example

In a department printer queue, tasks sent by the chair are printed first, followed by professors, then graduate students, and finally undergraduates.

Implementing Priority Queues Using Heaps

The standard approach is to use an array (or ArrayList) starting at position 1, where each item corresponds to one node in the heap.

Heap Array Representation

Root is always in array[1], left child in array[2], right child in array[3]. In general: if a node is in array[k], then its left child is in array[2k], right child in array[2k+1], and its parent in array[k/2].

Insert Operation

Add the new value at the end of the array (rightmost leaf), then use up-heapify (check-and-swap with parent) until the heap property holds.

RemoveMax Operation

Removes the root (largest element), replaces it with the last leaf, then restores heap order by swapping down (down-heapify).