# Problems

1. *<mark style="color:blue;">**Computational number theory.**</mark>* Write a program [CubeSum.java](https://algs4.cs.princeton.edu/24pq/CubeSum.java.html) that prints out all integers of the form $$a^3+b^3$$where $$a$$ and$$b$$𝑏 are integers between 0 and $$n<$$ in *sorted* order, without using excessive space. That is, instead of computing an array of the $$n^2$$ sums and sorting them, build a minimum-oriented priority queue, initially containing $$(0^3,0,0),(1^3+1^3,1,1),(2^3+2^3,2,2),…,(n^3+n^3,n,n)$$.  Then, while the priority queue is nonempty, remove the smallest item $$i^3+j^3,i,j)$$, print it, and then, if $$j\<n$$, insert the item $$(i^3+(j+1)^3,i,j+1)$$. Use this program to find all distinct integers $$a,b,c$$, and $$d$$ between 0 and $$10^6$$such that $$a^3+b^3=c^3+d^3$$𝑎3+𝑏3=, such as $$1729=9^3+10^3=1^3+12^3$$.

```cpp
#include <iostream>
using namespace std;

class cubeSum {

public:
     int i, j, sum;
     cubeSum(int i = 0, int j = 0) {
          this->sum = i * i * i + j * j * j;
          this->i = i;
          this->j = j;
     }
     int compareTo(const cubeSum &that) {
          if (this->sum > that.sum) return 1;
          else if (this->sum < that.sum) return -1;
          return 0;
     }
     string toString() {
          string res = to_string(sum) + " = " + to_string(i) + "^3" " + " + to_string(j) + "^3";
          return res;
     }
};

template <typename key>
class MinPQ {
     key *arr;
     int N;
     int i = 0;

     bool greeter(key &key1, key &key2) {
          return key1.compareTo(key2) > 0;
     }

     void swim(int k) {
          while (k > 1 && greeter(arr[k / 2], arr[k])) {
               swap(arr[k], arr[k / 2]);
               k = k / 2;
          }
     }

     void sink(int k) {
          while (2 * k <= i) {
               int j = 2 * k;

               if (j < i && greeter(arr[j], arr[j + 1])) j++; // find out which one is smaller 2k or 2k+1

               if (!greeter(arr[k], arr[j])) break; // break if the parent's key is smaller than both children's key

               swap(arr[k], arr[j]);
               k = j; // moving down the heap
          }
     }

public:
     MinPQ(int capacity) : N(capacity + 1) {
          arr = new key[capacity + 1]{NULL};
     }

     bool isEmpty() {
          return i == 0;
     }
     bool isFull() {
          return i == N - 1;
     }

     // At most 1 + lg N compares
     void insert(key val) {
          arr[++i] = val;
          swim(i);
     }

     // At most 2 lg N compares
     key delMin() {
          key min = arr[1];
          swap(arr[1], arr[i--]);
          sink(1);
          arr[i + 1] = NULL; // prevent loitering
          return min;
     }
};

int main() {
     int n = 4;
     MinPQ<cubeSum> *PQ = new MinPQ<cubeSum>(n);
     for (int i = 0; i < n; i++) {
          cubeSum cb(i, i);
          PQ->insert(cb);
     }

     while (!PQ->isEmpty()) {
          cubeSum s = PQ->delMin();
          if (s.j < n) {
               cubeSum cb(s.i, s.j + 1);
               PQ->insert(cb);
          }
          cout << s.toString() << endl;
     }
}
```

2. <mark style="color:blue;">**Index priority-queue implementation.**</mark> Implement [IndexMaxPQ.java](https://algs4.cs.princeton.edu/24pq/IndexMaxPQ.java.html) by modifying [MaxPQ.java](https://algs4.cs.princeton.edu/24pq/MaxPQ.java.html) as follows: Change pq\[] to hold indices, add an array keys \[ ] to hold the key values, and add an array qp\[] that is the inverse of pq \[] — qp\[i] gives the position of i in pq\[] (the index j such that pq\[j] is i). Then modify the code to maintain these data structures. Use the convention that qp\[i] is -1 if i is not on the queue, and include a method contains() that tests this condition. You need to modify the helper methods exch() and less() but not sink() or swim().

## [Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int size = 0;
        ListNode* temp;
        for(int i = 0; i < lists.size(); i++) {
            temp = lists[i];
            while(temp!=nullptr) {
                temp = temp -> next;
                size++;
            }
        }
        int* arr = new int[size];
        int j = 0;
        for(int i = 0; i < lists.size(); i++) {
            temp = lists[i];
            while(temp != nullptr) {
                arr[j++] = temp -> val;
                temp = temp -> next;
            }
        }

        heapSort(arr, size);
        
        ListNode* head = new ListNode(0);
        temp = head;

        for(int i = 0; i  < size; i++) {
            temp -> next = new ListNode(arr[i]);
            temp = temp -> next;
        }
        return head -> next;
    }

    
    void sink(int *arr, int k, int n)
    {
        while (k * 2 <= n)
        {
            int j = 2 * k;
            if (j < n && arr[j - 1] < arr[j])
                j++;
            if (!(arr[k - 1] < arr[j - 1]))
                break;

            swap(arr[k - 1], arr[j - 1]);
            k = j;
        }
    }
    
    void heapSort(int* arr, int size) {
        int N = size;

        for (int k = N / 2; k >= 1; k--)
            sink(arr, k, N);

        while (N > 1) {
            swap(arr[0], arr[--N]);
            sink(arr, 1, N);
        }
        
    }
};
```

## Q1: [ Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/)

```cpp
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int N = nums.size();
        // Bottom-Up 
        // Heap-Ordered
        for (int k = N / 2; k >= 1; k--)
            sink(nums, k, N);

        for(int i = 0; i < nums.size(); i++) {
          cout << nums[i] << " " ;
        }
        int i = nums.size()-1;
        int kthLargest = 0;
        while(k > 0) {
            kthLargest = delMax(nums, i);
            i--;
            k--;
        }
        return kthLargest;
    }

    int delMax(vector<int>& nums, int N) {
        int elem = nums[0];
        swap(nums[0], nums[N]);
        sink(nums, 1, N);
        N--;
        return elem;
    }

    void sink(vector<int>& nums, int k, int N) {
        while(2*k <= N) {
            int j = 2*k;
            if(j < N && nums[j-1] < nums[j]) j++;
            if(nums[k-1] > nums[j-1]) break;
            swap(nums[k-1], nums[j-1]);
            k = j;
        }
    }
};
```

## Q2: [Smallest Number in Infinite Set](https://leetcode.com/problems/smallest-number-in-infinite-set/)

```cpp
class SmallestInfiniteSet {
    priority_queue<int,vector<int>,greater<int>> pq;
    int arr[1001];
    
public:
    SmallestInfiniteSet() {
        for(int i = 1; i <= 1000; i++) {
            pq.push(i);
            arr[i] = 1;
        }
    }
    
    int popSmallest() {
        int ans = pq.top();
        pq.pop();
        arr[ans] = 0;
        return ans;
    }
    
    void addBack(int num) {
        if(arr[num] == 1) return;
        arr[num] = 1;
        pq.push(num);
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dsa-cpp.gitbook.io/nafees/priority-queue/problems.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.