Min-Heap to Max-Heap

Problem Statement

Write a Java program that modifies a min-heap-based priority queue implementation to support a max-heap, where larger values have higher priority. The program should enqueue integers into the max-heap and dequeue the largest element, printing each operation’s result. Test the modified implementation with various sequences of enqueue and dequeue operations, including edge cases like empty queues, single elements, and duplicate values. You can visualize this as a priority task list where the most urgent task (highest number) is always processed first, with the max-heap ensuring the largest value is at the root.

Input: A sequence of operations, where each operation is either:

• Enqueue: Add an integer to the max-heap (e.g., enqueue 5).
• Dequeue: Remove and return the largest element from the max-heap. Output: For each operation, print the action performed (enqueue or dequeue) and the result, such as the dequeued value or a message if the queue is empty. Constraints:
• Queue size is between 0 and 10^5.
• Elements are integers in the range [-10^9, 10^9].
• The queue may be empty when dequeue is called. Example:
• Input: Operations = [enqueue(3), enqueue(1), enqueue(4), dequeue, enqueue(2), dequeue]
• Output:

  Enqueued 3
  Enqueued 1
  Enqueued 4
  Dequeued: 4
  Enqueued 2
  Dequeued: 3
  

• Explanation: The max-heap ensures the largest element (4, then 3) is dequeued first.
• Input: Operations = [dequeue on empty queue]
• Output: Queue empty, cannot dequeue

Pseudocode

CLASS MaxPriorityQueue
    SET array to new integer array of size 1000
    SET size to 0
    
    FUNCTION enqueue(number)
        IF size equals array length THEN
            RETURN false (queue full)
        ENDIF
        SET array[size] to number
        CALL siftUp(size)
        INCREMENT size
        RETURN true
    ENDFUNCTION
    
    FUNCTION siftUp(index)
        WHILE index > 0
            SET parent to (index - 1) / 2
            IF array[index] <= array[parent] THEN
                BREAK
            ENDIF
            SWAP array[index] and array[parent]
            SET index to parent
        ENDWHILE
    ENDFUNCTION
    
    FUNCTION dequeue()
        IF size equals 0 THEN
            RETURN null (queue empty)
        ENDIF
        SET result to array[0]
        SET array[0] to array[size - 1]
        DECREMENT size
        IF size > 0 THEN
            CALL siftDown(0)
        ENDIF
        RETURN result
    ENDFUNCTION
    
    FUNCTION siftDown(index)
        SET maxIndex to index
        WHILE true
            SET left to 2 * index + 1
            SET right to 2 * index + 2
            IF left < size AND array[left] > array[maxIndex] THEN
                SET maxIndex to left
            ENDIF
            IF right < size AND array[right] > array[maxIndex] THEN
                SET maxIndex to right
            ENDIF
            IF maxIndex equals index THEN
                BREAK
            ENDIF
            SWAP array[index] and array[maxIndex]
            SET index to maxIndex
        ENDWHILE
    ENDFUNCTION
    
    FUNCTION isEmpty()
        RETURN size equals 0
    ENDFUNCTION
ENDCLASS

FUNCTION testMaxPriorityQueue(operations)
    CREATE queue as new MaxPriorityQueue
    FOR each operation in operations
        IF operation.type equals "enqueue" THEN
            IF queue.enqueue(operation.number) THEN
                PRINT enqueued number
            ELSE
                PRINT enqueue failed: queue full
            ENDIF
        ELSE IF operation.type equals "dequeue" THEN
            SET number to queue.dequeue()
            IF number is null THEN
                PRINT queue empty message
            ELSE
                PRINT dequeued number
            ENDIF
        ENDIF
    ENDFOR
ENDFUNCTION

FUNCTION main()
    SET testCases to array of operation sequences
    FOR each testCase in testCases
        PRINT test case details
        CALL testMaxPriorityQueue(testCase)
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a MaxPriorityQueue class using a max-heap with: a. An array to store integers, with size to track elements. b. enqueue: Add number to end, sift up to maintain max-heap property (larger values up). c. siftUp: Move larger number up if greater than parent. d. dequeue: Remove root (largest), move last element to root, sift down. e. siftDown: Move smaller number down to maintain max-heap property. f. isEmpty: Check if queue is empty.
2. In testMaxPriorityQueue: a. Create a MaxPriorityQueue. b. For each operation:
   • If "enqueue", add number, print action or "Queue full".
   • If "dequeue", remove largest number, print result or "Queue empty".
3. In main, test with sequences of enqueue and dequeue operations, including empty queues, single elements, and duplicates.

Java Implementation

import java.util.*;

public class MinHeapToMaxHeap {
    // Custom max-heap priority queue implementation
    static class MaxPriorityQueue {
        private int[] array;
        private int size;
        private static final int DEFAULT_SIZE = 1000;

        public MaxPriorityQueue() {
            array = new int[DEFAULT_SIZE];
            size = 0;
        }

        public boolean enqueue(int number) {
            if (size == array.length) {
                return false; // Queue full
            }
            array[size] = number;
            siftUp(size);
            size++;
            return true;
        }

        private void siftUp(int index) {
            while (index > 0) {
                int parent = (index - 1) / 2;
                if (array[index] <= array[parent]) {
                    break;
                }
                // Swap
                int temp = array[index];
                array[index] = array[parent];
                array[parent] = temp;
                index = parent;
            }
        }

        public Integer dequeue() {
            if (size == 0) {
                return null; // Queue empty
            }
            int result = array[0];
            array[0] = array[size - 1];
            size--;
            if (size > 0) {
                siftDown(0);
            }
            return result;
        }

        private void siftDown(int index) {
            int maxIndex = index;
            while (true) {
                int left = 2 * index + 1;
                int right = 2 * index + 2;
                if (left < size && array[left] > array[maxIndex]) {
                    maxIndex = left;
                }
                if (right < size && array[right] > array[maxIndex]) {
                    maxIndex = right;
                }
                if (maxIndex == index) {
                    break;
                }
                // Swap
                int temp = array[index];
                array[index] = array[maxIndex];
                array[maxIndex] = temp;
                index = maxIndex;
            }
        }

        public boolean isEmpty() {
            return size == 0;
        }
    }

    // Helper class for operations
    static class Operation {
        String type;
        Integer number;

        Operation(String type, Integer number) {
            this.type = type;
            this.number = number;
        }
    }

    // Tests max priority queue with operations
    public void testMaxPriorityQueue(List<Operation> operations) {
        MaxPriorityQueue queue = new MaxPriorityQueue();
        for (Operation op : operations) {
            if (op.type.equals("enqueue")) {
                if (queue.enqueue(op.number)) {
                    System.out.println("Enqueued " + op.number);
                } else {
                    System.out.println("Enqueue " + op.number + " failed: Queue full");
                }
            } else if (op.type.equals("dequeue")) {
                Integer number = queue.dequeue();
                if (number == null) {
                    System.out.println("Queue empty, cannot dequeue");
                } else {
                    System.out.println("Dequeued: " + number);
                }
            }
        }
    }

    // Main method to test max priority queue
    public static void main(String[] args) {
        MinHeapToMaxHeap tester = new MinHeapToMaxHeap();

        // Test cases
        List<List<Operation>> testCases = new ArrayList<>();
        
        // Test case 1: Normal sequence
        List<Operation> case1 = Arrays.asList(
            new Operation("enqueue", 3),
            new Operation("enqueue", 1),
            new Operation("enqueue", 4),
            new Operation("dequeue", null),
            new Operation("enqueue", 2),
            new Operation("dequeue", null)
        );
        testCases.add(case1);
        
        // Test case 2: Empty queue
        List<Operation> case2 = Arrays.asList(
            new Operation("dequeue", null)
        );
        testCases.add(case2);
        
        // Test case 3: Single element
        List<Operation> case3 = Arrays.asList(
            new Operation("enqueue", 5),
            new Operation("dequeue", null)
        );
        testCases.add(case3);
        
        // Test case 4: Duplicate values
        List<Operation> case4 = Arrays.asList(
            new Operation("enqueue", 2),
            new Operation("enqueue", 2),
            new Operation("enqueue", 2),
            new Operation("dequeue", null),
            new Operation("dequeue", null)
        );
        testCases.add(case4);

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            System.out.println("Test case " + (i + 1) + ":");
            tester.testMaxPriorityQueue(testCases.get(i));
            System.out.println();
        }
    }
}

Output

Running the main method produces:

Test case 1:
Enqueued 3
Enqueued 1
Enqueued 4
Dequeued: 4
Enqueued 2
Dequeued: 3

Test case 2:
Queue empty, cannot dequeue

Test case 3:
Enqueued 5
Dequeued: 5

Test case 4:
Enqueued 2
Enqueued 2
Enqueued 2
Dequeued: 2
Dequeued: 2

Explanation:

• Test case 1: Enqueues 3, 1, 4 (heap: [4,1,3]); dequeues 4; enqueues 2 (heap: [3,1,2]); dequeues 3.
• Test case 2: Dequeue on empty queue returns error.
• Test case 3: Enqueues 5, dequeues 5.
• Test case 4: Enqueues three 2’s, dequeues two 2’s in FIFO order.

How It Works

• MaxPriorityQueue:
  • Uses a max-heap array to maintain largest element at root.
  • enqueue: Adds to end, sifts up if larger than parent.
  • siftUp: Moves larger number up to maintain max-heap.
  • dequeue: Removes root, moves last element to root, sifts down.
  • siftDown: Moves smaller number down to maintain max-heap.
• testMaxPriorityQueue:
  • Enqueues numbers, printing action or "Queue full".
  • Dequeues largest number, printing result or "Queue empty".
• Example Trace (Test case 1):
  • Enqueue 3: array=[3], size=1.
  • Enqueue 1: array=[3,1], size=2.
  • Enqueue 4: array=[4,1,3], size=3 (after sift-up).
  • Dequeue: Returns 4, array=[3,1], size=2 (after sift-down).
  • Enqueue 2: array=[3,1,2], size=3.
  • Dequeue: Returns 3, array=[2,1], size=2.
• Main Method: Tests normal sequence, empty queue, single element, and duplicates.

Complexity Analysis Table

Note:

• n is the number of operations.
• Time complexity: O(log n) for enqueue/dequeue due to heap operations; O(n log n) for n operations.
• Space complexity: O(n) for storing up to n elements.
• Worst case: O(n log n) time, O(n) space for many operations.

✅ Tip: Convert a min-heap to a max-heap by reversing comparison logic to prioritize larger values. Test with duplicate values to verify FIFO behavior for equal priorities.

⚠ Warning: Ensure heap properties are maintained after each operation. Handle empty queue cases to avoid null pointer issues.