Unit 5: Heaps and Hashing - Subjective Questions

A heap is a specialized tree-based data structure that satisfies the complete binary tree property and the heap-order property.

• Structural property: A heap is a complete binary tree. Every level is completely filled except possibly the last level, which is filled from left to right.
• Max-heap property: The value of every parent node is greater than or equal to the values of its children. Therefore, the root contains the maximum element.
• Min-heap property: The value of every parent node is less than or equal to the values of its children. Therefore, the root contains the minimum element.

For an array representation using zero-based indexing, the relationships are:

• Parent of index :
• Left child of index :
• Right child of index :

Because a heap is complete, its height is .

A binary heap is commonly represented using an array because its complete binary tree structure does not require pointers or empty positions between nodes.

Consider the max-heap:

Its tree representation has as the root, and as its children, and , , and on the next level.

For zero-based indexing:

• The root is stored at index .
• The left child of index is stored at .
• The right child of index is stored at .
• The parent of index is stored at .

Advantages of array representation:

• No extra memory is required for links or pointers.
• Parent and child positions can be calculated directly.
• It provides good cache locality.
• Insertion and deletion can be performed in time.

Insertion into a max-heap is performed in two stages:

1. Insert the new element at the end of the array to preserve the complete binary tree property.
2. Repeatedly compare it with its parent and exchange them whenever the new element is greater. This process is called up-heap, sift-up, or percolate-up.

Initial heap:

Insert at the end:

The parent of is . Since , exchange them:

Now the parent of is . Since , the process stops.

The final max-heap is:

The worst-case time complexity is , while insertion may take when no exchange is required.

In a max-heap, deletion normally removes the root because it contains the maximum element.

Procedure:

1. Store the root element.
2. Replace the root with the last element.
3. Remove the last array position.
4. Compare the new root with its children.
5. Exchange it with the larger child whenever the child is greater.
6. Continue until the max-heap property is restored.

Initial heap:

Remove and move to the root:

The children of are and . Since is the larger child and , exchange them:

The max-heap property is now restored. The deleted value is .

This restoration process is called down-heap, sift-down, or heapify-down, and its worst-case time complexity is .

The bottom-up method builds a heap from an unsorted array by applying the heapify operation to all non-leaf nodes.

For an array of elements using zero-based indexing, the last non-leaf node is at:

Heapify is applied from this index down to index .

Algorithm:

• Treat the input array as a complete binary tree.
• Start from the last non-leaf node.
• Apply sift-down to restore the heap property in its subtree.
• Continue toward the root.

A loose bound of is obtained by multiplying nodes by work. However, most nodes are close to the leaves and require very little work. The total cost can be expressed as:

Since converges to a constant, the total time is:

Thus, bottom-up heap construction is more efficient than inserting all elements separately, which would require time in the worst case.

Heap sort is a comparison-based sorting algorithm that uses a binary heap. To sort in ascending order, it constructs a max-heap.

Phase 1: Build a max-heap

• Convert the unsorted array into a max-heap.
• The largest element is then located at the root.
• Bottom-up heap construction requires time.

Phase 2: Repeated extraction

• Exchange the root with the last element in the current heap.
• Reduce the heap size by one, leaving the largest element in its final position.
• Apply sift-down to the new root.
• Repeat until only one heap element remains.

The extraction phase performs approximately heapify operations, each requiring at most time. Therefore:

Complexities and properties:

• Best-case time:
• Average-case time:
• Worst-case time:
• Auxiliary space: for an iterative in-place implementation
• Stability: Heap sort is not stable
• Adaptiveness: It is not adaptive to an already sorted input

To sort the array in ascending order, first construct a max-heap.

Initial array:

After bottom-up max-heap construction:

Extraction steps:

1. Exchange with the last element and heapify the reduced heap:

2. Exchange with the last element of the reduced heap and heapify:

3. Exchange with the last element of the reduced heap and heapify:

4. Exchange with :

The final sorted array is:

The algorithm takes time and can be implemented using auxiliary space.

Hashing is a technique for mapping a key to a table location so that insertion, search, and deletion can be performed efficiently.

• A hash function transforms a key into a valid table index. It is commonly written as .
• A hash table is an array of slots or buckets used to store records according to their hash values.
• A collision occurs when two different keys produce the same table index. That is, for :

For example, if , the keys and both map to index .

Hashing is useful because it provides expected time for insertion, search, and deletion when the hash function distributes keys uniformly and the load factor is controlled. Its worst-case time can become when many keys collide.

A good hash function should have the following characteristics:

• Deterministic: The same key must always produce the same index.
• Uniform: Keys should be distributed evenly across the table.
• Fast: The function should be inexpensive to compute.
• Range-limited: It must produce an index between and for a table of size .
• Key-sensitive: It should use relevant parts of the key and reduce patterns that cause clustering.

Common construction methods:

• Division method:
  
  A prime value of is often selected to reduce regular patterns.

• Multiplication method:
  
  where .

• Mid-square method: Square the key and select digits or bits from the middle of the result.

• Folding method: Divide the key into equal-sized parts and add or combine the parts.

No hash function completely eliminates collisions for arbitrary keys when the key space is larger than the table.

In the division method, the hash value is obtained by taking the remainder after dividing the key by the table size :

For a table of size :

Thus, and collide at index .

A prime table size is generally preferred because it is less likely to share common factors with patterns in the keys. For example, if keys are mostly multiples of and the table size is also a multiple of , only a small subset of slots may be used.

The table size should normally avoid values with strong relationships to the key pattern, such as powers of when only lower-order bits are being used. Choosing an appropriate prime often improves distribution, although the quality of the complete hash function still depends on the nature of the keys.

The load factor measures how full a hash table is. If keys are stored in a table with slots, then:

For separate chaining:

• Each slot stores a chain of elements.
• The load factor may be less than, equal to, or greater than .
• Under uniform hashing, the expected chain length is approximately .
• Expected search time is approximately .

For open addressing:

• Every key is stored directly in the table array.
• The load factor must satisfy .
• Performance degrades rapidly as approaches because longer probe sequences are required.
• Rehashing is commonly performed when the load factor crosses a chosen threshold.

Therefore, controlling the load factor is essential for maintaining expected constant-time hash-table operations.

Open hashing, commonly called separate chaining, resolves collisions by storing a collection of keys at each table index. The collection is often implemented as a linked list, but a dynamic array or balanced tree may also be used.

Insertion:

• Compute .
• Insert the new record into the chain at index .
• Inserting at the beginning of a linked list takes time if duplicate checking is not required.

Search:

• Compute .
• Traverse the chain at index until the key is found or the chain ends.

Deletion:

• Locate the key in its chain.
• Remove the corresponding node by updating links.

Under uniform hashing, the expected operation time is , where . In the worst case, all keys may enter the same chain, causing operation time.

Separate chaining can store more elements than the number of table slots, but it requires additional memory for chain structures.

Separate chaining and open addressing resolve collisions in different ways.

Separate chaining is convenient when the number of records is unpredictable. Open addressing is useful when memory locality and low pointer overhead are important, provided the load factor is controlled.

Closed hashing, also called open addressing, stores every record directly within the hash-table array. When a collision occurs, a probe sequence is used to inspect alternative slots.

A general probe function is written as:

where is the probe number.

Insertion:

• Generate successive positions using the probe function.
• Insert the key into the first empty or reusable deleted slot.
• Report failure or resize the table if no suitable slot exists.

Search:

• Follow exactly the same probe sequence used during insertion.
• Stop when the key is found, an unused empty slot is encountered, or all relevant slots have been examined.

Deletion:

• A deleted slot should not normally be changed directly to an unused empty slot because this could break the probe sequence of another key.
• Instead, mark it with a special deleted marker or tombstone.

Open addressing has good cache locality but becomes inefficient as the load factor approaches .

In linear probing, collisions are resolved by examining consecutive table positions. The probe function is:

where is the initial hash value and .

Let , , and insert , , and :

• maps to index and is inserted there.
• also maps to . Index is occupied, so it is inserted at index .
• maps to . Indices and are occupied, so it is inserted at index .

The resulting occupied block is at indices , , and .

Primary clustering is the formation of long consecutive groups of occupied slots. Any new key hashing anywhere near such a group tends to join it, causing the group to grow and increasing search and insertion time.

Linear probing is simple and cache-friendly, but primary clustering is its main disadvantage.

In quadratic probing, the distance from the original hash position increases quadratically. A common probe function is:

A simpler form is:

For example, if , the probe offsets are . The examined positions are obtained by adding these offsets modulo .

Advantages:

• It spreads probes more widely than linear probing.
• It reduces primary clustering because colliding keys do not simply occupy consecutive slots.

Limitations:

• Keys with the same initial hash value follow the same probe sequence. This is called secondary clustering.
• Depending on , , and , the probe sequence may not visit every table slot.
• Insertion may fail even when some table positions are empty.
• Performance declines at high load factors.

Appropriate table-size and coefficient choices are necessary to ensure that a useful portion of the table is examined.

Double hashing uses a second hash function to determine the step size between probes. Its probe function is:

For example, consider:

If , then and . The probe positions are modulo .

A good secondary hash function should satisfy these conditions:

• It must never produce a step size of .
• Its value should depend on the key.
• The step size should be relatively prime to the table size so that all slots can potentially be visited.
• It should distribute step sizes uniformly.

Double hashing significantly reduces both primary and secondary clustering and generally produces probe behavior close to uniform hashing.

The three methods are forms of open addressing, but they generate different probe sequences.

Probe behavior:

• Linear probing uses a fixed step of one.
• Quadratic probing uses increasing quadratic offsets.
• Double hashing uses a key-dependent step size.

In general, double hashing gives the best distribution among these techniques. Linear probing can still perform well at low load factors because of good memory locality. Quadratic probing provides a compromise but requires suitable parameters.

Deletion is difficult in open addressing because keys displaced by collisions depend on an uninterrupted probe sequence.

Suppose key hashes to index and key also hashes to index . If occupies index , may be inserted at index . If is deleted and index is marked as completely empty, a later search for may stop at index and incorrectly report that is absent.

A tombstone is a special marker indicating that a slot previously contained a key but was deleted.

• During search, a tombstone does not terminate the probe sequence.
• During insertion, a tombstone can usually be reused.
• An unused empty slot still terminates an unsuccessful search.

Too many tombstones increase probe lengths and reduce performance. Therefore, implementations may periodically rebuild or rehash the table to remove tombstones.

Rehashing is the process of creating a new hash table and reinserting existing keys using the new table size and corresponding hash indices.

Rehashing may be required when:

• The load factor exceeds a selected threshold.
• Open-addressing probe sequences become too long.
• Separate-chaining lists become excessively large.
• Too many tombstones accumulate.
• The table needs to shrink after many deletions.

Steps involved:

1. Allocate a new table, commonly about twice the old size.
2. Choose a suitable new size, often a prime number.
3. Initialize all slots or buckets in the new table.
4. Traverse the old table.
5. Recompute the hash position of every active key using the new table size.
6. Insert each active key into the new table.
7. Discard the old table after migration.

Keys cannot simply be copied to the same indices because the hash value commonly depends on the table size. A single rehash costs , but occasional resizing can provide expected amortized insertion time.