<h1
style="
display: flex;
align-items: center;
justify-content: center;"
>
DSaA Lab 8 - Heaps and Priority Queues
</h1>

<h4 style="text-align: center;">
The Islamic University of Gaza<br>
Engineering Faculty<br>
Department of Computer Engineering
</h4>

<font color="#ec53c4">
Prepared by:
Eng. Ahmad Albarasy
</font>
<br>
<font color="#ec53c4">
Under the supervision of:
Prof. Ahmad Mahdi
</font>

---
In this lab, we are going to explore heaps, one of the most important applications of tree-based data structures which provides an efficient way to organize data based on priority, making them a fundamental component in many real-world systems and algorithms. We are also going to study priority queues, which rely on heaps to support fast insertion and removal of the highest (or lowest) priority elements.

## The Priority Queue

### Definition
A priority queue is **an abstract data type (ADT) in which each element is associated with a priority**, and elements are accessed or removed based on their priority rather than their insertion order.

Unlike a regular queue (FIFO), where the first inserted element is the first removed, a priority queue always removes the element with the highest priority (or the lowest priority, depending on the convention).

/**
 * An interface for a priority queue, where each element has an associated key
 * that determines its priority.
 */
public interface PriorityQueue<K, V> {

  /**
   * Returns the number of entries in the priority queue.
   */
  int size();

  /**
   * Tests whether the priority queue is empty.
   */
  boolean isEmpty();

  /**
   * Inserts a key-value pair into the priority queue 
   * and returns the entry created.
   */
  Entry<K, V> insert(K key, V value) throws IllegalArgumentException;

  /**
   * Returns (but does not remove) an entry with minimal key.
   */
  Entry<K, V> min();

  /**
   * Removes and returns an entry with minimal key.
   */
  Entry<K, V> removeMin();
}

### Implementation

A priority queue is an abstract data type and can be implemented using several underlying data structures. Each implementation offers different performance characteristics for insertion, access, and removal operations.

#### 1. Unsorted List or Array

In this approach, elements are stored in an unsorted collection.

- **Insertion:** `O(1)`, since the element can be appended at the end.
- **Find-Min / Remove-Min:** `O(n)`, since the entire list must be scanned to find the minimum.

This implementation is simple but inefficient for frequent removals.

#### 2. Sorted List or Array

Here, elements are maintained in sorted order.

- **Insertion:** `O(n)`, since elements must be shifted to maintain order.
- **Find-Min:** `O(1)`, if the smallest element is kept at one end.
- **Remove-Min:** `O(1)` or `O(n)`, depending on whether shifting is required.

This approach is efficient when insertions are rare.

#### 3. Binary Search Tree

**A balanced binary search tree** (such as a red-black tree or AVL tree) can be used to implement a priority queue.

- **Insertion:** `O(log n)`
- **Find-Min:** `O(log n)`
- **Remove-Min:** `O(log n)`

This provides good performance but requires a more complex structure.

#### 4. Binary Heap (Most Common)

The most common and efficient implementation of a priority queue is the heap implementation.

- **Insertion:** `O(log n)`
- **Find-Min:** `O(1)`
- **Remove-Min:** `O(log n)`

The heap offers an excellent balance between simplicity and efficiency, which is why it is widely used in practice.

### Real-World Use Cases

Priority queues are used in many real-world systems where elements must be processed according to importance, urgency, or cost rather than arrival time.

#### 1. Task Scheduling in Operating Systems
Operating systems use priority queues to decide which process should run next. Processes with higher priority (such as system-critical tasks) are scheduled before lower-priority background tasks.

#### 2. Network Packet Routing
Routers and switches use priority queues to process network packets. Time-sensitive data such as video calls or voice traffic is given higher priority than less urgent data like file downloads.

#### 3. Graph Algorithms
Algorithms such as Dijkstra’s shortest path and Prim’s minimum spanning tree rely on priority queues to efficiently select the next node with the smallest distance or cost.

#### 4. Emergency and Service Systems
Hospitals and emergency response systems use priority queues to treat patients or incidents based on severity rather than arrival time.

#### 5. Artificial Intelligence and Search Algorithms
AI search strategies such as A* use priority queues to explore the most promising states first based on heuristic values.

## The Heap

### Definition

A heap is **a specialized complete binary tree** that ensures that the maximum (in a max-heap) or minimum (in a min-heap) element is always stored at the root of the tree, which allows efficient access to the highest- or lowest-priority element.

The way heaps maintain such a property is achieved as follows:

1. **Every node satisfies the heap property:**
* In a max-heap, the value of each node is greater than or equal to the values of its children
* In a min-heap, the value of each node is less than or equal to the values of its children.

<div style="text-align: center; margin-bottom:10px">
<img src="https://hackmd.io/_uploads/ryLm-n0NZe.png" alt="image">
</div>

2. **The heap is always kept complete**, meaning that all levels are fully filled except possibly the last, which is filled from left to right.

### Fundamental and Auxiliary Operations

Heaps support a small set of fundamental operations that define their main functionality and a set of auxiliary operations that are used internally to maintain the heap structure and its properties.

#### Fundamental Operations

* **Insertion:** Adds a new element `x` to the heap while preserving the heap structure and heap property.
* **Find-Min / Find-Max:** Returns the minimum element in a min-heap or the maximum element in a max-heap without removing it.
* **Remove-Min / Remove-Max:** Removes and returns the root element (minimum or maximum), then restores the heap structure.

#### Auxiliary Operations

* **Upheap (Bubble-Up / Percolate-Up):** Moves a newly inserted element upward until the heap property is restored.
* **Downheap (Bubble-Down / Percolate-Down):** Moves the root element downward after removal until the heap property is restored.
* **Swap:** Exchanges two elements in the underlying array representation.

The efficiency of these operations is closely related to the height of the heap. Since a heap is a complete binary tree, its height is `O(logn)`, where `n` is the number of elements. As a result, insertion and removal operations run in `O(logn)` time due to the upheap and downheap processes, while accessing the minimum or maximum element takes `O(1)` time because it is always stored at the root.

### Implementation

/**
 * An implementation of a priority queue using an array-based heap.
 */
public class HeapPriorityQueue<K, V> extends AbstractPriorityQueue<K, V> {

  /** Primary collection of priority queue entries */
  protected ArrayList<Entry<K, V>> heap = new ArrayList<>();

  /** Creates an empty priority queue
   * based on the natural ordering of its keys. */
  public HeapPriorityQueue() {
    super();
  }

  /** Creates an empty priority queue
   * using the given comparator to order keys. */
  public HeapPriorityQueue(Comparator<K> comp) {
    super(comp);
  }

  // protected utilities

  protected int parent(int j) {
    return (j - 1) / 2;
  }

  protected int left(int j) {
    return 2 * j + 1;
  }

  protected int right(int j) {
    return 2 * j + 2;
  }

  protected boolean hasLeft(int j) {
    return left(j) < heap.size();
  }

  protected boolean hasRight(int j) {
    return right(j) < heap.size();
  }

  /** Exchanges the entries at indices i and j of the array list. */
  protected void swap(int i, int j) {
    Entry<K, V> temp = heap.get(i);
    heap.set(i, heap.get(j));
    heap.set(j, temp);
  }

  /** Moves the entry at index j higher,
   * if necessary, to restore the heap property. */
  protected void upheap(int j) {
    while (j > 0) {
      int p = parent(j);
      if (compare(heap.get(j), heap.get(p)) >= 0) break;
      swap(j, p);
      j = p;
    }
  }

  /** Moves the entry at index j lower,
   * if necessary, to restore the heap property. */
  protected void downheap(int j) {
    while (hasLeft(j)) {
      int leftIndex = left(j);
      int smallChildIndex = leftIndex;

      if (hasRight(j)) {
        int rightIndex = right(j);
        if (compare(heap.get(leftIndex), heap.get(rightIndex)) > 0) {
          smallChildIndex = rightIndex;
        }
      }

      if (compare(heap.get(smallChildIndex), heap.get(j)) >= 0) break;

      swap(j, smallChildIndex);
      j = smallChildIndex;
    }
  }

  // public methods

  /** Returns the number of items in the priority queue. */
  public int size() {
    return heap.size();
  }

  /** Returns (but does not remove) an entry with minimal key (if any). */
  public Entry<K, V> min() {
    if (heap.isEmpty()) return null;
    return heap.get(0);
  }

  /** Inserts a key-value pair and returns the entry created. */
  public Entry<K, V> insert(K key, V value)
    throws IllegalArgumentException {
    checkKey(key);
    Entry<K, V> newest = new PQEntry<>(key, value);
    heap.add(newest);
    upheap(heap.size() - 1);
    return newest;
  }

  /** Removes and returns an entry with minimal key (if any). */
  public Entry<K, V> removeMin() {
    if (heap.isEmpty()) return null;
    Entry<K, V> answer = heap.get(0);
    swap(0, heap.size() - 1);
    heap.remove(heap.size() - 1);
    downheap(0);
    return answer;
  }
}

## The Heap Sort

### Definition

Heap sort is a **comparison-based sorting algorithm** that uses a heap to efficiently sort an array. It works by first building a max-heap from the array, then repeatedly removing the maximum element from the heap and placing it at the end of the array. Building a max-heap from an existing linear sequence (typically an array) happens in-place without using an extra container, making the process memory-efficient.

### Algorithm Steps

1. **Build a max-heap** from the input array.
2. **Swap the root (maximum element) with the last element** of the heap.
3. **Reduce the heap size** by one and restore the heap property using downheap (heapify) on the new root.
4. Repeat steps 2–3 until the heap is empty.

public class HeapSort {

  // Main function to perform heap sort
  public static void heapSort(int[] arr) {
    int n = arr.length;

    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
      heapify(arr, n, i);
    }

    // Extract elements from heap one by one
    for (int i = n - 1; i >= 0; i--) {
      int temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;

      // Heapify reduced heap
      heapify(arr, i, 0);
    }
  }

  // Heapify a subtree rooted at index i
  private static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
      largest = left;

    if (right < n && arr[right] > arr[largest])
      largest = right;

    if (largest != i) {
      int swap = arr[i];
      arr[i] = arr[largest];
      arr[largest] = swap;

      // Recursively heapify affected sub-tree
      heapify(arr, n, largest);
    }
  }
}

### Complexity

- **Time Complexity:** `O(n log n)` for all cases.
- **Space Complexity:** `O(1)` extra space for array-based implementation (in-place sort).

## Tasks

### Task 1 (4 points)

Given an integer array `nums` and an integer `k`, return the kth largest element in the array.

**Note** that it is the kth largest element in the sorted order, not the kth distinct element.

Question link on [LeetCode](https://leetcode.com/problems/kth-largest-element-in-an-array)

Example 1:

>Input: nums = `[3,2,1,5,6,4]`, k = `2`
>Output: `5`

Example 2:

>Input: nums = `[3,2,3,1,2,4,5,5,6]`, k = `4`
>Output: `4`

**Constraints:**

* `1` <= `k` <= `nums.length` <= `105`
* `-104` <= `nums[i]` <= `104`

---

### Task 2 (6 points)

Given an integer array `nums` and an integer `k`, return the `k` most frequent elements. You may return the answer in any order.

Question link on [LeetCode](https://leetcode.com/problems/top-k-frequent-elements)

Example 1:

>Input: nums = `[1,1,1,2,2,3]`, k = `2`
>Output: `[1,2]`

Example 2:

>Input: nums = `[1]`, k = `1`
>Output: `[1]`

Example 3:

>Input: nums = `[1,2,1,2,1,2,3,1,3,2]`, k = `2`
>Output: `[1,2]`

**Constraints:**

* `1` <= `nums.length` <= `105`
* `-104` <= `nums[i]` <= `104`
* `k` is in the range `[1, the number of unique elements in the array]`
* It is guaranteed that the answer is unique

---

### Tasks Submission Guide

You will solve both problems on LeetCode and you have to make sure that your solution passes all test cases and that LeetCode accepts it. Once you are done, its time to submit your solution on GradeScope.

Firstly, make sure to submit only two files:
**1. TaskOne.java
2. TaskTwo.java**

Secondly, for each question, you have to follow these steps to make sure GradeScope's autograder runs without issues:

#### For Task 1:

1. Copy your whole solution into a file named `TaskOne.java`
2. Change the class name from `Solution` to `TaskOne`, and make sure that the class is public
3. add the following package identifier to the beginning of the file. Make sure to copy it and **don't write it manually to avoid typos**:

package com.gradescope.labEight;

Here's an example solution for reference:

package com.gradescope.labEight;

public class TaskOne {
  public int findKthLargest(int[] nums, int k) {
  
  }
  /* if any helper methods are needed, make sure to include them */
}

#### For Task 2:

1. Copy your whole solution into a file named `TaskTwo.java`
2. Change the class name from `Solution` to `TaskTwo`, and make sure that the class is public
3. add the following package identifier to the beginning of the file. Make sure to copy it and **don't write it manually to avoid typos**:

package com.gradescope.labEight;

Here's an example solution for reference:

package com.gradescope.labEight;

public class TaskTwo {
  public int[] topKFrequent(int[] nums, int k) {

  }
  /* if any helper methods are needed, make sure to include them */
}

---

<div
style="display: flex;
align-items: center;
justify-content: center;"
>
Happy Coding 🙂
</div>