Priority Queues

An abstract data type (ADT) that stores elements with priorities.

A value from a totally ordered universe (like numbers) used to determine the importance of an element in a PrioQueue. The smaller the priority value, the higher the importance.

A method that adds a new element with a specific priority to a PrioQueue.

A method that removes and returns the element with the smallest priority from a PrioQueue.

A method that checks whether a PrioQueue is empty.

A binary tree where elements are ordered and smaller or equal to their children. All levels except the last one are completely filled, and the last level has left-aligned nodes.

A node in a binary tree that has no children. It's the bottom level.

In a binary heap, this ensures that all levels except the last one are completely filled, and the last level has left-aligned nodes.

The node that has no parent node, found at the top of the binary tree.

The node that has at least one child node. All nodes except the leaf nodes are inner nodes.

A method that inserts a new element (key) into a binary heap. It places the element at the rightmost position of the last level and then bubbles it up towards the root to maintain heap ordering.

Used to keep track of the index of the last element in the binary heap, effectively indicating the end of the heap structure.

A method that compares an element with its parent and swaps them if the ordering property is violated. It traverses upwards recursively until the element finds its correct position in the heap.

A characteristic of binary heaps requiring that the parent node's key is always smaller than or equal to its children's keys. This is true for min-heaps and vice versa for max-heaps.

A method that inserts a new element with a specific key and value into a priority queue. The key is used to determine the element's priority in the queue.

A method that returns the element with the smallest key from a priority queue and removes it from the queue.

A sorting algorithm that utilizes a priority queue to sort an array of elements by their priority.

A type of priority queue implementation that uses a linear ordering of linked nodes. In this variant, elements are stored in increasing order, making extracting the minimum element very efficient.

Another type of linked nodes implementation where elements are stored in an arbitrary order. Here, inserting elements is very efficient, but finding the minimum element is expensive.

A technique used in the linked nodes implementation to simplify the process of extracting the minimum element. It involves introducing a dummy node, which is a placeholder and never removed from the list.

A priority queue implementation that utilizes an array instead of linked nodes. Array implementations typically offer better running times and caching behavior.

A non-linear data structure that consists of nodes, each potentially storing an element. Binary trees are used in implementations of priority queues based on arrays.

The time complexity of an algorithm is estimated based on the time it takes to complete its operations. This estimate is represented using Big-O notation, which summarizes the growth rate of an algorithm's running time as the input size increases.

A sorting algorithm categorizes elements according to their values, arranging them from smallest to largest. This can be achieved by placing elements into a sorted list or rearranging them within an array. The insertion sort method is one such algorithm.

Heapsort is a sorting algorithm that utilizes a binary heap data structure. The algorithm works by repeatedly extracting the smallest element from the heap (the root) and replacing it with the last element, then restoring heap order. This process continues until all elements are sorted.

In-place algorithms perform operations on data directly within the original memory space. This means they do not create temporary arrays or copies of data, modifying the input data directly. For example, when applying in-place sorting to an array, the sorted results are stored in the same array, without needing additional memory.

The stability of a sorting algorithm refers to whether it preserves the original relative order of elements with equal values while sorting. If a stable algorithm sorts elements with the same value, elements that were originally in the order A then B will remain that way after sorting. An unstable algorithm might change the positions of equal elements, even if they were originally in order.

In a heap, the element with the smallest priority is moved to the end of the heap and swapped with the last element. The size of the heap is reduced by one. The element at the root position is then 'bubbled down' to maintain the heap property.

A recursive function that ensures the heap property is maintained after a deletion operation by moving the element at the root downwards to its correct position. It compares the element with its children and swaps it with the smaller child if necessary.

This represents the maximum depth of a binary tree, which in the case of a heap, represents the maximum number of steps an element needs to be 'bubbled down' in a worst-case scenario.

This algorithm sorts an array using a priority queue. It first inserts all elements into the priority queue, then repeatedly extracts the minimum element from the queue and places it back into the array.

The time complexity of the insert operation for a specific implementation of a priority queue.

The time complexity of the extractMin operation for a specific implementation of a priority queue.

The total running time of the prioQueueSort() algorithm.

The running time of the prioQueueSort() algorithm depends on the running time of the insert and extractMin operations in the chosen priority queue implementation. In the worst-case scenario, it is proportional to the number of elements (n).