第七道:(215) Kth Largest Element in an Array

Solving Method: Quick Select, Quick Sort, sort, min heap, max heap 

Key points: priority queue, min heap

Quick Select

code:

1. sort method

```python
nums.sort()
        return nums [len (nums)-k]
```

2. quick select 

```python
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        if k == 50000: return 1
        k = len(nums) - k # target index
        def quickSelect(l, r):
            pivot, p = nums[r], l  # Use the last element as the pivot
            for i in range(l, r):
                if nums[i] <= pivot:
                    nums[p], nums[i] = nums[i], nums[p]
                    p += 1
            nums[r], nums[p] = nums[p], nums[r]  # Place pivot in its correct position
            
            if p > k:  # Target index is on the left part
                return quickSelect(l, p - 1)
            elif p < k:  # Target index is on the right part
                return quickSelect(p + 1, r)
            else:  # Found the target index
                return nums[p]
        
        return quickSelect(0, len(nums) - 1)
```

3. Min heap

```python
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = [] #min-heap
        for i in nums:
            if len(heap) < k: #if current size of heap is less than k, it adds to the heap and maintains the min-heap property
                heapq.heappush(heap, i)
            else:
                if i > heap[0]:
                    heapq.heappop(heap) #pop() = removes 
                    heapq.heappush(heap, i) #push() = adds
        return heap[0]
```
Example: 

input **`nums = [3, 2, 1, 5, 6, 4]`** and **`k = 2`**

### **Step-by-Step Execution:**

1. **Initial State:**
    - **`nums = [3, 2, 1, 5, 6, 4]`**
    - **`k = 2`**
    - **`heap = []`**
2. **Iteration 1:**
    - Current **`num = 3`**
    - **`heap`** size is less than **`k`** (2), so we add **`3`** to the heap.
    - **`heap = [3]`**
3. **Iteration 2:**
    - Current **`num = 2`**
    - **`heap`** size is less than **`k`**, so we add **`2`** to the heap.
    - **`heap = [2, 3]`**
    - Note: The heap is a min-heap, so the smallest element is at the root.
4. **Iteration 3:**
    - Current **`num = 1`**
    - **`heap`** size is equal to **`k`**, so we compare **`1`** with the smallest element in the heap (**`2`**).
    - **`1`** is not greater than **`2`**, so we do nothing.
    - **`heap = [2, 3]`**
5. **Iteration 4:**
    - Current **`num = 5`**
    - **`heap`** size is equal to **`k`**, so we compare **`5`** with the smallest element in the heap (**`2`**).
    - **`5`** is greater than **`2`**, so we remove **`2`** and add **`5`** to the heap.
    - **`heap = [3, 5]`**
6. **Iteration 5:**
    - Current **`num = 6`**
    - **`heap`** size is equal to **`k`**, so we compare **`6`** with the smallest element in the heap (**`3`**).
    - **`6`** is greater than **`3`**, so we remove **`3`** and add **`6`** to the heap.
    - **`heap = [5, 6]`**
7. **Iteration 6:**
    - Current **`num = 4`**
    - **`heap`** size is equal to **`k`**, so we compare **`4`** with the smallest element in the heap (**`5`**).
    - **`4`** is not greater than **`5`**, so we do nothing.
    - **`heap = [5, 6]`**

### **Final State:**

- **`heap = [5, 6]`**
- The smallest element in the heap (**`heap[0]`**) is **`5`**.

what I’ve learned from this question:

### **Min Heap**

- **Definition:** A min heap is a binary tree where the parent node is always less than or equal to its children.
- **Key Property:** The smallest element is always at the root of the tree.
- **Example:**
    
    ```markdown
    markdownCopy code
        1
       / \
      3   2
     / \
    5   4
    
    ```
    

### **Max Heap**

- **Definition:** A max heap is a binary tree where the parent node is always greater than or equal to its children.
- **Key Property:** The largest element is always at the root of the tree.
- **Example:**
    
    ```markdown
    markdownCopy code
        9
       / \
      5   8
     / \
    2   4
    
    ```
    

### **Summary**

- **Min Heap:** Root is the smallest element.
- **Max Heap:** Root is the largest element.