Merge `M` sorted lists each containing `N` elements
Given m sorted lists, each containing n elements, print them efficiently in sorted order.
Tag: Priority Queue
Find the smallest range with at least one element from each of the given lists
Given M sorted lists of variable length, efficiently compute the smallest range, including at least one element from each list.
Find k’th smallest element in an array
Given an array and a positive integer k, find k’th smallest element in the array… We can easily solve this problem in O(n.log(k)) time by using a max-heap.
Sort a k-sorted array
Given a k–sorted array that is almost sorted such that each of the n elements may be misplaced by no more than k positions from the correct sorted order. Find a space-and-time efficient algorithm to sort the array.
Find k’th largest element in an array
Given an array and positive integer k, find k’th largest element in the array.
Heap Sort Algorithm – Overview & C, C++, Java, and Python Implementation
Heapsort is an in-place, comparison-based sorting algorithm and can be thought of as an improved selection sort as it divides the input into a sorted and an unsorted region.
Min Heap and Max Heap Implementation in C++
In previous post, we have introduced the heap data structure and covered heapify-up, push, heapify-down and pop operations. This article covers C++ implementation of Priority Queue Data Structure (Max Heap and Min heap).
Introduction to Priority Queues using Binary Heaps
A priority queue is an ADT (Abstract Data Type) for maintaining a set S of elements, with each element having a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority or vice versa.
Single-Source Shortest Paths – Dijkstra’s Algorithm
Given a source vertex s from a set of vertices V in a weighted graph where all its edge weights w(u, v) are non-negative, find the shortest path weights d(s, v) from source s for all vertices v present in the graph.