Chương trình C++ tìm phần tử lớn thứ k trong dãy

Trong chương trình này, chúng ta cần trích xuất phần tử lớn thứ K từ một dãy. Độ phức tạp thời gian của kỹ thuật này có thể được cải thiện bằng cách tiếp cận vấn đề sử dụng max-heap (đối tối đa). Độ phức tạp thời gian của chương trình là O(n + k*log n).

Thuật toán

Bắt đầu
  Gửi phần tử lớn nhất của heap đến cuối dãy.
  Heapify phần dãy còn lại.
  Lặp lại quá trình 'k' lần.
  In trạng thái cuối cùng của mảng.
  In phần tử lớn nhất từ heap được trích xuất từ lần lặp thứ k như kết quả.
Kết thúc.

Mã ví dụ

#include <iostream>
using namespace std;

void MaxHeapify(int a[], int i, int n) {
    int j, t;
    t = a[i];
    j = 2*i;
    while (j <= n) {
        if (j < n && a[j+1] > a[j])
            j = j+1;
        if (t > a[j])
            break;
        else if (t <= a[j]) {
            a[j/2] = a[j];
            j = 2*j;
        }
    }
    a[j/2] = t;
    return;
}

void Build_MaxHeapify(int a[], int n) {
    int i;
    for (i = n/2; i >= 1; i--)
        MaxHeapify(a, i, n);
}

int main() {
    int n, i, temp, k;
    cout << "\nNhập số lượng phần tử dữ liệu cần sắp xếp: ";
    cin >> n;
    n++;
    int arr[n];
    for (i = 1; i < n; i++) {
        cout << "Nhập phần tử " << i << ": ";
        cin >> arr[i];
    }
    cout << "\nNhập giá trị k: ";
    cin >> k;
    Build_MaxHeapify(arr, n-1);
    for (i = n-1; i >= n-k; i--) {
        temp = arr[i];
        arr[i] = arr[1];
        arr[1] = temp;
        MaxHeapify(arr, 1, i - 1);
    }
    cout << "\nSau khi max-heapify mảng đã cho " << k << " lần trạng thái mảng là: ";
    for (i = 1; i < n; i++)
        cout << "->" << arr[i];
    cout << "\n\nPhần tử lớn thứ " << k << " là: " << arr[n-k];
    return 0;
}

Kết quả

Nhập số lượng phần tử dữ liệu cần sắp xếp: 5
Nhập phần tử 1: 20
Nhập phần tử 2: 10
Nhập phần tử 3: 30
Nhập phần tử 4: 70
Nhập phần tử 5: 60
Nhập giá trị k: 2
Sau khi max-heapify mảng đã cho 2 lần trạng thái mảng là: ->30->20->10->60->70
Phần tử lớn thứ 2 là: 60