Priority Queue

Space	Time
	Access	Lookup	Insertion	Deletion
O(n)	O(n)	O(n)	O(1)	O(1)

Definition

Short

Priority Queue is a data structure that allows elements to be inserted and removed based on their priority.

Simplified

You're planning your day with a list of tasks: grocery shopping, work meeting, gym, cooking dinner, and reading a book. However, not all tasks are equally important. Some tasks are urgent and need to be done first, while others can wait.

In this scenario, a "Priority Queue" is like a smart to-do list. It helps you manage your tasks based on their importance or urgency. The task with the highest priority (like a work meeting) gets to be at the front of the queue, meaning it should be done first. Once that task is completed, it's removed from the queue, and the next highest priority task (like grocery shopping) moves to the front.

Detailed

Priority Queue is a specialized data structure. It functions like a regular queue or stack, but each element also has an associated "priority". Elements with higher priority are processed before those with lower priority. If elements share the same priority, they're handled in their queue order.

Priority queues and heaps are often mentioned together, but they're not the same. A priority queue is an abstract concept, like a list or a map, and can be implemented in various ways, including using a heap or an unordered array.

Practice

Practice

Aspect	Pseudo Code
Heapify Up	heapify_up(index): if index == 0: return parent_index = (index - 1) / 2 if heap[parent_index].value < heap[index].value: swap(heap, parent_index, index) heapify_up(parent_index)
Heapify Down	heapify_down(): index = 0 while index < heap.size: left_child_index=2 * index + 1 right_child_index = 2 * index + 2 smallest_index = -1 if heap.size > left_child_index and heap[left_child_index].value < heap[index].value: smallest_index = left_child_index else if heap.size > right_child_index and heap[right_child_index].value < heap[index].value: smallest_index = right_child_index else: break swap(heap, index, smallest_index) index = smallest_index method swap(list, i, j): temp = list[i] list[i] = list[j] list[j] = temp
Enqueue	enqueue(item, priority): heap.add(Pair(item, priority)) heapify_up(heap.last_index)
Dequeue	dequeue(): if heap == ø: return ø highest_priority_item = heap[0].key heap[0] = heap.last() heap.remove_at(heap.last_index) heapify_down() return highest_priority_item
Peek	peek(): if heap == ø: return ø else: return heap[0].key
Change Priority	change_priority(item, new_priority): index = heap.find_index(item) if index != -1: heap[index] = Pair(item, new_priority) heapify_up(index)
Find by Value	find_by_value(item: T): T?: index = heap.find_index(item) if index != -1: return heap[index].key else: return ø

Solution

package main

import "container/heap"

type Item struct {
	Value    interface{}
	Priority int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].Priority < pq[j].Priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(*Item)
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func NewPriorityQueue() *PriorityQueue {
	pq := make(PriorityQueue, 0)
	heap.Init(&pq)
	return &pq
}

func (pq *PriorityQueue) Enqueue(value interface{}, priority int) {
	heap.Push(pq, &Item{Value: value, Priority: priority})
}

func (pq *PriorityQueue) Dequeue() interface{} {
	if pq.Len() == 0 {
		return nil
	}
	return heap.Pop(pq).(*Item).Value
}

func (pq *PriorityQueue) Peek() interface{} {
	if pq.Len() == 0 {
		return nil
	}
	return (pq[0]).Value
}

func (pq *PriorityQueue) ChangePriority(value interface{}, newPriority int) {
	for i := 0; i < pq.Len(); i++ {
		if pq[i].Value == value {
			pq[i].Priority = newPriority
			heap.Fix(pq, i)
			break
		}
	}
}

func (pq *PriorityQueue) FindByValue(value interface{}) interface{} {
	for i := 0; i < pq.Len(); i++ {
		if pq[i].Value == value {
			return pq[i].Value
		}
	}
	return nil
}

import java.util.*;

class PriorityQueue<T> {

  private List<Pair<T, Integer>> heap = new ArrayList<>();

  public void enqueue(T item, int priority) {
    heap.add(new Pair<>(item, priority));
    heapifyUp();
  }

  public T dequeue() {
    if (heap.isEmpty()) {
      return null;
    }
    T highestPriorityItem = heap.get(0).getKey();
    heap.set(0, heap.get(heap.size() - 1));
    heap.remove(heap.size() - 1);
    heapifyDown();
    return highestPriorityItem;
  }

  public T peek() {
    if (heap.isEmpty()) {
      return null;
    }
    return heap.get(0).getKey();
  }

  public void changePriority(T item, int newPriority) {
    int index = findIndexByItem(item);
    if (index != -1) {
      heap.set(index, new Pair<>(item, newPriority));
      heapifyUp(index);
    }
  }

  public T findByValue(T item) {
    int index = findIndexByItem(item);
    if (index != -1) {
      return heap.get(index).getKey();
    }
    return null;
  }

  private void heapifyUp(int index) {
    if (index == 0) {
      return;
    }
    int parentIndex = (index - 1) / 2;
    if (heap.get(parentIndex).getValue() < heap.get(index).getValue()) {
      swap(heap, parentIndex, index);
      heapifyUp(parentIndex);
    }
  }

  private void heapifyDown() {
    int index = 0;
    while (index < heap.size()) {
      int leftChildIndex = 2 * index + 1;
      int rightChildIndex = 2 * index + 2;
      int smallestIndex = findSmallestIndex(leftChildIndex, rightChildIndex);
      if (smallestIndex == -1) {
        break;
      }
      swap(heap, index, smallestIndex);
      index = smallestIndex;
    }
  }

  private void swap(List<Pair<T, Integer>> list, int i, int j) {
    Pair<T, Integer> temp = list.get(i);
    list.set(i, list.get(j));
    list.set(j, temp);
  }

  private int findIndexByItem(T item) {
    for (int i = 0; i < heap.size(); i++) {
      if (heap.get(i).getKey().equals(item)) {
        return i;
      }
    }
    return -1;
  }

  private int findSmallestIndex(int leftChildIndex, int rightChildIndex) {
    if (leftChildIndex >= heap.size()) {
      return -1;
    }
    if (rightChildIndex >= heap.size()) {
      return leftChildIndex;
    }
    int leftPriority = heap.get(leftChildIndex).getValue();
    int rightPriority = heap.get(rightChildIndex).getValue();
    return leftPriority < rightPriority ? leftChildIndex : rightChildIndex;
  }
}

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

  enqueue(item, priority) {
    this.heap.push([item, priority]);
    this.heapifyUp();
  }

  dequeue() {
    if (this.heap.length === 0) {
      return null;
    }
    const highestPriorityItem = this.heap[0][0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapifyDown();
    return highestPriorityItem;
  }

  peek() {
    if (this.heap.length === 0) {
      return null;
    }
    return this.heap[0][0];
  }

  changePriority(item, newPriority) {
    const index = this.findIndexByItem(item);
    if (index !== -1) {
      this.heap[index][1] = newPriority;
      this.heapifyUp(index);
    }
  }

  findByValue(item) {
    const index = this.findIndexByItem(item);
    if (index !== -1) {
      return this.heap[index][0];
    }
    return null;
  }

  heapifyUp(index = this.heap.length - 1) {
    if (index === 0) {
      return;
    }
    const parentIndex = Math.floor((index - 1) / 2);
    if (this.heap[parentIndex][1] < this.heap[index][1]) {
      this.swap(this.heap, parentIndex, index);
      this.heapifyUp(parentIndex);
    }
  }

  heapifyDown() {
    let index = 0;
    while (index < this.heap.length) {
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;
      const smallestIndex = this.findSmallestIndex(
        leftChildIndex,
        rightChildIndex,
      );
      if (smallestIndex === -1) {
        break;
      }
      this.swap(this.heap, index, smallestIndex);
      index = smallestIndex;
    }
  }

  swap(list, i, j) {
    const temp = list[i];
    list[i] = list[j];
    list[j] = temp;
  }

  findIndexByItem(item) {
    for (let i = 0; i < this.heap.length; i++) {
      if (this.heap[i][0] === item) {
        return i;
      }
    }
    return -1;
  }

  findSmallestIndex(leftChildIndex, rightChildIndex) {
    if (leftChildIndex >= this.heap.length) {
      return -1;
    }
    if (rightChildIndex >= this.heap.length) {
      return leftChildIndex;
    }
    const leftPriority = this.heap[leftChildIndex][1];
    const rightPriority = this.heap[rightChildIndex][1];
    return leftPriority < rightPriority ? leftChildIndex : rightChildIndex;
  }
}

class PriorityQueue<T> {
    private val heap: MutableList<Pair<T, Int>> = mutableListOf()

    fun enqueue(item: T, priority: Int) {
        heap.add(Pair(item, priority))
        heapifyUp()
    }

    fun dequeue(): T? {
        if (heap.isEmpty()) {
            return null
        }
        val highestPriorityItem = heap[0].first
        heap[0] = heap.last()
        heap.removeAt(heap.lastIndex)
        heapifyDown()
        return highestPriorityItem
    }

    fun peek(): T? {
        return if (heap.isEmpty()) {
            null
        } else {
            heap[0].first
        }
    }

    fun changePriority(item: T, newPriority: Int) {
        val index = heap.indexOfFirst { it.first == item }
        if (index != -1) {
            heap[index] = Pair(item, newPriority)
            heapifyUp(index)
        }
    }

    fun findByValue(item: T): T? {
        val index = heap.indexOfFirst { it.first == item }
        return if (index != -1) {
            heap[index].first
        } else {
            null
        }
    }

    private fun heapifyUp(index: Int = heap.lastIndex) {
        if (index == 0) {
            return
        }
        val parentIndex = (index - 1) / 2
        if (heap[parentIndex].second < heap[index].second) {
            swap(heap, parentIndex, index)
            heapifyUp(parentIndex)
        }
    }

    private fun heapifyDown() {
        var index = 0
        while (index < heap.size) {
            val leftChildIndex = 2 * index + 1
            val rightChildIndex = 2 * index + 2
            val smallestIndex = when {
                leftChildIndex < heap.size && heap[leftChildIndex].second < heap[index].second -> leftChildIndex
                rightChildIndex < heap.size && heap[rightChildIndex].second < heap[index].second -> rightChildIndex
                else -> break
            }
            swap(heap, index, smallestIndex)
            index = smallestIndex
        }
    }

    private fun swap(list: MutableList<Pair<T, Int>>, i: Int, j: Int) {
        val temp = list[i]
        list[i] = list[j]
        list[j] = temp
    }
}

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def enqueue(self, item, priority):
        self.heap.append((priority, item))
        self._heapify_up()

    def dequeue(self):
        if not self.heap:
            return None
        highest_priority_item = self.heap[0][1]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self._heapify_down()
        return highest_priority_item

    def peek(self):
        if not self.heap:
            return None
        return self.heap[0][1]

    def change_priority(self, item, new_priority):
        for i, (priority, value) in enumerate(self.heap):
            if value == item:
                self.heap[i] = (new_priority, item)
                self._heapify_up(i)
                break

    def find_by_value(self, item):
        for priority, value in self.heap:
            if value == item:
                return value
        return None

    def _heapify_up(self, index=None):
        if index is None:
            index = len(self.heap) - 1
        if index == 0:
            return
        parent_index = (index - 1) // 2
        if self.heap[parent_index][0] < self.heap[index][0]:
            self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
            self._heapify_up(parent_index)

    def _heapify_down(self):
        index = 0
        while index < len(self.heap):
            left_child_index = 2 * index + 1
            right_child_index = 2 * index + 2
            smallest_index = index
            if left_child_index < len(self.heap) and self.heap[left_child_index][0] < self.heap[smallest_index][0]:
                smallest_index = left_child_index
            if right_child_index < len(self.heap) and self.heap[right_child_index][0] < self.heap[smallest_index][0]:
                smallest_index = right_child_index
            if smallest_index == index:
                break
            self.heap[index], self.heap[smallest_index] = self.heap[smallest_index], self.heap[index]
            index = smallest_index

use std::cmp::Ordering;

struct PriorityQueue<T> {
    heap: Vec<(T, i32)>,
}

impl<T> PriorityQueue<T> {
    fn new() -> Self {
        PriorityQueue { heap: Vec::new() }
    }

    fn enqueue(&mut self, item: T, priority: i32) {
        self.heap.push((item, priority));
        self.heapify_up();
    }

    fn dequeue(&mut self) -> Option<T> {
        if self.heap.is_empty() {
            return None;
        }
        let highest_priority_item = self.heap.swap_remove(0).0;
        self.heapify_down();
        Some(highest_priority_item)
    }

    fn peek(&self) -> Option<&T> {
        self.heap.get(0).map(|(item, _)| item)
    }

    fn change_priority(&mut self, item: T, new_priority: i32) {
        if let Some(index) = self.heap.iter().position(|(existing_item, _)| existing_item == &item) {
            self.heap[index] = (item, new_priority);
            self.heapify_up(index);
        }
    }

    fn find_by_value(&self, item: &T) -> Option<&T> {
        self.heap.iter().find_map(|(existing_item, _)| {
            if existing_item == item {
                Some(existing_item)
            } else {
                None
            }
        })
    }

    fn heapify_up(&mut self, mut index: usize) {
        while index > 0 {
            let parent_index = (index - 1) / 2;
            if self.heap[parent_index].1 < self.heap[index].1 {
                self.heap.swap(parent_index, index);
                index = parent_index;
            } else {
                break;
            }
        }
    }

    fn heapify_down(&mut self) {
        let mut index = 0;
        while let Some(left_child_index) = 2 * index + 1 < self.heap.len().then(|| 2 * index + 1) {
            let right_child_index = 2 * index + 2;
            let smallest_index = match right_child_index < self.heap.len().then(|| right_child_index) {
                Some(right_index) if self.heap[right_index].1 > self.heap[left_child_index].1 => right_index,
                _ => left_child_index,
            };
            if self.heap[smallest_index].1 > self.heap[index].1 {
                self.heap.swap(index, smallest_index);
                index = smallest_index;
            } else {
                break;
            }
        }
    }
}

class PriorityQueue<T> {
  private heap: Array<[T, number]> = [];

  enqueue(item: T, priority: number): void {
    this.heap.push([item, priority]);
    this.heapifyUp();
  }

  dequeue(): T | null {
    if (this.heap.length === 0) {
      return null;
    }
    const highestPriorityItem: T = this.heap[0][0];
    this.heap[0] = this.heap.pop()!;
    this.heapifyDown();
    return highestPriorityItem;
  }

  peek(): T | null {
    return this.heap.length === 0 ? null : this.heap[0][0];
  }

  changePriority(item: T, newPriority: number): void {
    const index = this.heap.findIndex(
      ([existingItem, _]) => existingItem === item,
    );
    if (index !== -1) {
      this.heap[index] = [item, newPriority];
      this.heapifyUp(index);
    }
  }

  findByValue(item: T): T | null {
    const index = this.heap.findIndex(
      ([existingItem, _]) => existingItem === item,
    );
    return index !== -1 ? this.heap[index][0] : null;
  }

  private heapifyUp(index: number = this.heap.length - 1): void {
    if (index === 0) {
      return;
    }
    const parentIndex = Math.floor((index - 1) / 2);
    if (this.heap[parentIndex][1] < this.heap[index][1]) {
      this.swap(parentIndex, index);
      this.heapifyUp(parentIndex);
    }
  }

  private heapifyDown(): void {
    let index = 0;
    while (index < this.heap.length) {
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;
      const smallestIndex =
        leftChildIndex < this.heap.length &&
        this.heap[leftChildIndex][1] < this.heap[index][1]
          ? leftChildIndex
          : rightChildIndex < this.heap.length &&
              this.heap[rightChildIndex][1] < this.heap[index][1]
            ? rightChildIndex
            : -1;

      if (smallestIndex !== -1) {
        this.swap(index, smallestIndex);
        index = smallestIndex;
      } else {
        break;
      }
    }
  }

  private swap(i: number, j: number): void {
    const temp = this.heap[i];
    this.heap[i] = this.heap[j];
    this.heap[j] = temp;
  }
}