{"id":9149,"date":"2022-07-19T10:16:43","date_gmt":"2022-07-19T10:16:43","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9149"},"modified":"2022-12-14T10:33:53","modified_gmt":"2022-12-14T10:33:53","slug":"kth-smallest-element-in-an-unsorted-array-using-priority-queue","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/kth-smallest-element-in-an-unsorted-array-using-priority-queue\/","title":{"rendered":"Kth Smallest Element In An Unsorted Array Using Priority Queue"},"content":{"rendered":"

\"\"<\/p>\n

Problem Statement:<\/h3>\n

The problem statement is straightforward as we have an array of size n and we have to find the kth<\/sup> smallest element in an unsorted array using priority queue.<\/p>\n

Example:<\/strong>
\nInput: n = 5
\nK = 2
\nArray = [50, 30, 70, 80, 100]<\/p>\n

            Output: 50 (As 50 is the second smallest element in the array)<\/code><\/pre>\n
Priority Queue<\/a>:<\/h3>\n
Priority queue is an abstract data type, It is a type of queue in which each element has a priority assigned to it. The priority of the element determines the order in which elements are removed from the priority queue. In the priority queue, all the elements are arranged either in ascending order or descending order.<\/p>\n
Priority Queue Properties:<\/h3>\n
    \n
  • In the priority queue, every element has priority assigned to it.<\/li>\n
  • The element with highest priority first.<\/li>\n
  • If two elements are having the same priority then they are served according to their order in the queue.<\/li>\n<\/ul>\n
    Approach:<\/h3>\n
    The approach is quite simple: we’ll use max-heap to find the kth<\/sup> smallest element in an unsorted array.<\/p>\n
    Algorithm:<\/h3>\n
      \n
    • Implement a max-heap.<\/li>\n
    • Insert first k elements of the array into the max-heap. (A[0\u2026.k-1])<\/li>\n
    • For the remaining element of the array. (A[k\u2026.n-1])\n
        \n
      • Insert the element one by one in a max-heap and check if the size of the max-heap is greater than k.<\/li>\n
      • If so, pop the element from the top.<\/li>\n
      • Repeat the above process till the array becomes empty.<\/li>\n<\/ul>\n<\/li>\n
      • Then, return the top most element of the max-heap i.e. kth smallest element of the array.<\/li>\n<\/ul>\n\t\t\t\t\t\t