Binary Heap Data Structure

Binary Heap

• Binary Heap is a binary tree with two main properties.

Shape Property

• Must be a complete binary tree
• Complete binary trees have all levels fully filled except possibly the last level, which is filled from left to right.

Heap Property

• In a Min Heap, every node is less than or equal to its children.
• In a Max Heap, every node is greater than or equal to its children.

Applications of Heaps

• Can implement priority queues
• Selecting the Kth element
• Efficient sorting (used in heapsort)

Insertion in a Binary Heap

• An element is inserted into the heap while maintaining the complete tree structure and heap property.

Insertion Steps

• Find the insertion point, going from left to right on the last level
• Traverse the tree level-order until the first node with an available child spot, this is O(n)
• Insert the new node as the left or right child, depending on what's available
• Bubble Up (Heapify Up) while the inserted nodes value is less than its parent like in a Min Heap
  • Swap the two nodes
  • Move up to the parent and repeat

Deletion in a Binary Heap

• An element is removed from the heap while maintaining the complete tree structure and heap property.
• Only the minimum in min heap or maximum in max heap element can be removed.

Deletion Steps

• Swap root with the last node in the tree, this is the rightmost node on the last level
• Remove the last node, formerly the root
• Bubble Down (Heapify Down), starting at the new root
  • If the node is greater than either of its children
  • Swap it with the smaller child like in a Min Heap
  • Repeat until it's smaller than both or is a leaf

Heaps as Arrays

• Binary heaps can be implemented more easily using an array instead of a tree with nodes and pointers.
• Binary heaps are complete binary trees, which means they have a predictable, compact structure that fits perfectly into a flat array
• Tree representations require level-order traversal to find where to insert, which is already an O(n) operation
• Managing node objects and pointers is required with trees.
• Heapifying requires complex swapping logic with parent/child nodes in trees.
• If a node is at index i:
  • The left child is at 2i + 1
  • The right child is at 2i + 2
  • The parent is at floor((i-1)/2)

Methods

• int getLeftIdx(int i) gives the left child of the parent i
• int getRightIdx(int i) gives the right child of the parent i
• int getParentIdx(int i) gives the parent of the child i
• T getMin() returns the minimum element of the min heap
• void deleteMin() deletes the minimum element of the min heap
• void insert(T k) inserts a given element k at the appropriate index

Hashing

• Hashing is a technique used to map data to a fixed-size value, called a hash code or hash value and is used for fast data access, insertion, and deletion.
• Hashing is the backbone of hash tables, which allow for average-case constant time (O(1)) operations.

Hash Functions

• A hash function takes a key and returns an index in the hash table.

Requirements of a Good Hash Function

• Deterministic: Same input always gives the same output.
• Efficient: Fast to compute.
• Uniform: Distributes keys evenly across the table.
• Minimizes collisions: Two different keys should ideally not hash to the same index.

Collisions

• A collision occurs when two different keys hash to the same index.

Collision Resolution Strategies

• Chaining (Separate Chaining)
  • Each bucket stores a linked list, easy to implement and table size doesn't limit the number of elements
  • Potentially slower if many items hash to the same index.
• Open Addressing
  • Finds the next available slot in the table itself.

Common Open Addressing Strategies

• Linear Probing: Check the next index = ((i + k) % tableSize) continuously until a free spot is found, where i is the index the key was originally hashed to and k is the number of previous collisions for that key
• Quadratic Probing: Check index = (i + c1 * k + c2 * k²) % tableSize continuously until a free spot is found, where i is the original index from the hash function, k is the number of previous collisions for that key, and c1 and c2 are constants
• Double Hashing: Use a second hash function to decide the step size using index = (i + k * h2(key)) % tableSize. where h2 is the second hash function and k the number of collisions thus far

Load Factor

Load Factor (a) = number of elements / table size

• Helps measure how full the table is.
• As a approaches 1, collision chances increase.
• Rehashing is the process of creating a new table, typically with the nearest prime number to double the original table size and then re-inserting all elements using the new table and hash function in order to keep operations efficient as the data grows.

Picking a Table Size

• Using key % size when the size is not prime can lead to clustering.
• Clustering is when keys hash to nearby locations to form large blocks, causing slower operations.
• With quadratic probing, non-prime sizes can cause repeated or skipped indices, leaving some slots unreachable.
• Table sizes with prime numbers minimize these modular arithmetic patterns, ensuring a more uniform spread of keys.

Picking a Collision Resolution Strategy

• Chaining (Separate Chaining)
  • Each bucket holds a list of entries, easy to implement, handles high load factors, but requires extra memory
• Open Addressing: All entries are stored in the table itself.
  • Linear Probing: probes next slot: (i + k) % tableSize which is simple but suffers from primary clustering, degrading performance as the table fills.
• Quadratic Probing: Probes using: (i + c1 * k + c2 * k^2) % tableSize which reduces primary clustering and offers a better spread, but suffers from secondary clustering and is harder to implement deletions.
• Deleting an item in open addressing can break the probe sequence, leading to incorrect search results.
• A deleted slots must be marked with a tombstone placeholder to fix this and indicate that the slot was occupied but is now deleted, needing probing to continue when looking for different keys.
• Tombstones preserve the integrity of the probe sequence but add complexity, as the table must now distinguish between: empty (slot never used), tombstone (deleted slot), occupied (active key)
• Double Hashing: Probes using a second hash function: (i + k * h2(key)) % tableSize, minimizing clustering and offering unique probe sequences, requiring two good hash functions.

Collision Resolution Strategy Comparison

• Chaining: High Extra Space, Low Clustering Risk, Unlimited Load Factor Limit, Easy Deletion Handling
• Linear Probing: None Extra Space, High Clustering Risk, ~0.7 max Load Factor Limit, Tricky (tombstones) Deletion Handling
• Quadratic Probing: None Extra Space, Medium Clustering Risk, ~0.5-0.7 Load Factor Limit, Tricky (tombstones) Deletion Handling
• Double Hashing: None Extra Space, Low Clustering Risk, ~0.7 Load Factor Limit, Tricky (tombstones) Deletion Handling

Runtime of Hash Map Operations

In ideal scenarios, hash tables provide constant-time operations.

• Search: O(1) Average/Best Case, O(n) Worst Case
• Insert: O(1) Average/Best Case, O(n) Worst Case
• Delete: O(1) Average/Best Case, O(n) Worst Case

Applications of Hashing

• Dictionaries/Maps
• Database indexing
• Caching
• Symbol tables in compilers
• Password storage