unit.10

Unit Overview

• This unit covers the following topics:

  • Priority Queue ADT

  • Heap data structure

  • Binomial Queue data structure

  • HeapSort

Priority Queue

• Definition: A priority queue is an Abstract Data Type (ADT) that supports two primary operations:

  • void insert(Key v): Inserts a key into the priority queue.

  • E delMax(): Returns and removes the key with the highest priority, where:

    • Max Priority Queue: Highest priority means largest value.

    • Min Priority Queue: Highest priority means smallest value.

Characteristics of Priority Queues

• The priority can be based on any type that can be compared using relational operators (==, !=, <, >, <=, >=).

• It is distinct from a regular queue due to its operational differences.

Max Priority Queue Class Structure

• class MaxPQ<Key> has the following methods:

  • MaxPQ(): Create a priority queue.

  • MaxPQ(int max): Initialize with a capacity of max.

  • MaxPQ(Key a[]): Create from an array of keys.

  • void insert(Key v): Insert key.

  • Key max(): Return the largest key.

  • Key delMax(): Return and remove the largest key.

  • bool isEmpty(): Check if the queue is empty.

  • int size(): Get number of keys in the queue.

Implementation of Priority Queue

• Insert and delMax operations can be implemented through different data structures:

  • Unordered Linked List: Insert O(1), delMax O(n)

  • Ordered Linked List: Insert O(n), delMax O(1)

  • Unordered Array: Insert O(1), delMax O(n)

  • Ordered Array: Insert O(n), delMax O(1)

Heaps

• Definition: A heap is a binary tree characterized by:

  • Ordering Property: A node's key is at least as large as its children (heap-ordered).

  • The highest key is always the root.

  • Structural Property: The binary tree must be complete.

Full vs. Complete Binary Trees

• Full Binary Tree: Every node other than leaves has two children; it has 2^h - 1 nodes.

• Complete Binary Tree: Each level is fully filled except possibly the last, with nodes as far left as possible.

Binary Heap

• A binary heap is arranged in a complete heap-ordered binary tree and represented in an array using level order.

• Its height is approximately ⌊log2 N⌋.

Inserting in a Priority Queue

• To insert, add the key in the first empty position on the last row.

• Example: Before and after the insertion of 9 in the heap shows the effects on structure and ordering properties.

Swim Method

• After insertion, if the new node violates the ordering property, it is swapped with its parent until it reaches the root or the parent key is higher.

• Example steps demonstrate how the ordering property is restored.

delMax Operation

• To delete the maximum key, we copy the last node's key into the root and delete the last node. This may violate the ordering property which is then restored using the Sink method.

Sink Method

• This method adjusts the heap back to order by swapping a node with the greater of its children until the ordering property is satisfied.

Priority Queue Code Structure

• Implements methods for the priority queue operations:

  • Code Template for MaxPQ class outlines necessary methods and accompanying flows for swim and sink operations.

Running Time Analysis

• In an N-key priority queue,:

  • Insert: O(1 + log N) comparisons.

  • delMax: O(log N) comparisons.

Sorting Using Heap

• A heap can be used for sorting an array by inserting all elements into the heap and removing them one at a time, achieving a complexity of O(n log n).

Heapify

• Process of building a heap from an array; can be done via:

  • A) swim method: O(n log n)

  • B) sink method: O(n) (faster option)

Binomial Queue

• A binomial queue is a forest of power-of-two heaps with unique sizes for heaps present. Construction relates to binary representation of sizes.

• Merging Heaps involves making the root of one heap the child of another while preserving properties and managing priorities.

Run Times of Binomial Queue Operations

• Merging two heaps takes constant time, merging two bins takes O(log n), and deletion involves finding the heap with the highest key, needing O(log n) for both locating and deletion.