Is PriorityQueue in C# a min-heap or a max-heap?

A min-priority queue: Dequeue() and Peek() return the element whose priority compares lowest, so after enqueuing 7, 2, 9, 4, 11 with each value as its own priority the head is 2. For a max-heap pass a reversed comparer to the constructor, new PriorityQueue (Comparer .Create((x, y) => y.CompareTo(x))), and the head becomes 11. Element and priority are separate type parameters, which is why every call here passes the number twice. UnorderedItems enumerates the backing array, not sorted order, so only repeated Dequeue() calls give the values in order.

How do I return the kth smallest element instead?

From the sorted clone read sorted[k - 1], which is 4 for [7, 2, 9, 4, 11] and k = 2. With the queue, build it with the reversed comparer above so it is a max-heap of the k smallest values and EnqueueDequeue evicts the largest; Peek() ends at 4 as well. For quickselect leave the partition as it is and set int target = a.Length - k.

Can I find the kth largest element with LINQ?

nums.OrderByDescending(x => x).Skip(k - 1).First() returns 9 for [7, 2, 9, 4, 11] and k = 2, and nums.OrderByDescending(x => x).Take(k) gives the top k, 8, 6, 6 for [6, 6, 1, 8, 3] with k = 3. Both read well, but OrderByDescending is the sort approach in disguise: it buffers and sorts the whole sequence, O(n log n), before the first value comes out. In hot code the loops above are cheaper.

What happens if k is larger than the array?

Each version fails differently. Sorting [3, 1] and asking for k = 5 reads index -3 and throws IndexOutOfRangeException. The queue version throws nothing: it never reaches k items, so Peek() returns 1, a plausible but wrong answer. With k = 0 the queue stays empty and Peek() throws InvalidOperationException. A guard as the first line, if (k nums.Length) throw new ArgumentOutOfRangeException(nameof(k));, gives every version one clear failure.

Why is quickselect O(n²) in the worst case?

The pivot rule is fixed, always the middle index, so an input can be built where each pivot is the largest or smallest value in the window and every pass discards a single element; n shrinking passes add up to about n² comparisons. Picking the pivot with Random.Shared.Next(lo, hi) makes that pattern practically impossible to hit, at the cost of a result order that can differ between runs, and median-of-medians gives a true O(n) worst case with larger constant factors. The sort and queue versions do not depend on pivot luck.

Kth Largest Element in C#: Sort, PriorityQueue and Quickselect

find_kth_largest.cs

C# 10.0

Not run yet

+ 6 hidden

Input

nums = [7, 2, 9, 4, 11]
k = 2

Expected

From largest to smallest the array is 11, 9, 7, 4, 2, and the 2nd value is 9.