ASSIGNMENT-1
1. What is a Heap?
A heap is a complete binary tree stored as an array with a special property:
Max-Heap: Every node ≥ its children → root is the maximum element.
Min-Heap: Every node ≤ its children → root is the minimum element.
For a 0-based array arr:
Parent of i → (i - 1) / 2
Le child of i → 2 * i + 1
Right child of i → 2 * i + 2
2. Heap Sort (Using a Max-Heap)
Goal: Sort an array in ascending order.
Steps:
1. Build a Max-Heap from the array.
2. Repeat un l heap size becomes 1:
o Swap arr[0] (largest element) with arr[last index]
o Reduce heap size by 1 (ignore last sorted part)
o Heapify from index 0 to fix the heap.
Example array:
[12, 11, 13, 5, 6, 7]
Build max-heap → [13, 11, 12, 5, 6, 7] (conceptually)
Swap root with last → [7, 11, 12, 5, 6, 13], heapify → [12, 11, 7, 5, 6, 13]
Repeat un l fully sorted → [5, 6, 7, 11, 12, 13]
3. Priority Queue Using a Heap
A Priority Queue is like a normal queue but elements come out in order of priority, not just FIFO.
If we use a Max-Heap:
insert(x) → put at end, then “bubble up” (heapify up)
getMax() / top() → return heap[0]
extractMax() / pop() → remove root, move last to root, “heapify down”
So a Max-Heap is a natural way to implement a Priority Queue.
4. C++ Code: Heap Sort + Priority Queue (Using Max-Heap)
#include <iostream>
#include <vector>
using namespace std;
void heapify(vector<int> &arr, int n, int i) {
int largest = i;
int le = 2 * i + 1;
int right = 2 * i + 2;
if (le < n && arr[le ] > arr[largest])
largest = le ;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
void heapSort(vector<int> &arr) {
int n = [Link]();
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
class MaxHeapPriorityQueue {
private:
vector<int> heap;
int parent(int i) { return (i - 1) / 2; }
int le Child(int i) { return 2 * i + 1; }
int rightChild(int i) { return 2 * i + 2; }
void heapifyUp(int i) {
while (i != 0 && heap[parent(i)] < heap[i]) {
swap(heap[i], heap[parent(i)]);
i = parent(i);
void heapifyDown(int i) {
int n = [Link]();
while (true) {
int largest = i;
int le = le Child(i);
int right = rightChild(i);
if (le < n && heap[le ] > heap[largest])
largest = le ;
if (right < n && heap[right] > heap[largest])
largest = right;
if (largest != i) {
swap(heap[i], heap[largest]);
i = largest;
} else {
break;
public:
bool empty() const { return [Link](); }
void push(int value) {
heap.push_back(value);
heapifyUp([Link]() - 1);
int top() const {
if ([Link]())
throw run me_error("Priority queue is empty");
return heap[0];
int pop() {
if ([Link]())
throw run me_error("Priority queue is empty");
int maxValue = heap[0];
heap[0] = [Link]();
heap.pop_back();
if (![Link]())
heapifyDown(0);
return maxValue;
void printHeap() const {
cout << "Current heap (array representa on): ";
for (int x : heap)
cout << x << " ";
cout << "\n";
};
int main() {
vector<int> arr = {12, 11, 13, 5, 6, 7};
cout << "===== HEAP SORT DEMONSTRATION =====\n";
cout << "Original array: ";
for (int x : arr) cout << x << " ";
cout << "\n";
heapSort(arr);
cout << "Sorted array (ascending) using Heap Sort: ";
for (int x : arr) cout << x << " ";
cout << "\n\n";
cout << "===== PRIORITY QUEUE USING MAX-HEAP =====\n";
MaxHeapPriorityQueue pq;
cout << "Inser ng elements: 10, 40, 20, 5, 60, 30\n";
[Link](10);
[Link](40);
[Link](20);
[Link](5);
[Link](60);
[Link](30);
[Link]();
cout << "Current max (top): " << [Link]() << "\n\n";
cout << "Extrac ng elements in order of priority:\n";
while (![Link]()) {
cout << [Link]() << " ";
cout << "\n";
return 0;
OUTPUT: