Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include<math.h>
- using namespace std;
- void siftDown(int *a, int i, int n, int k)
- {
- int j, m;
- m = a[i];
- j = 2 * i;
- while (j <= n)
- {
- if (j < n && a[j + 1] > a[j])
- j = j + 1;
- if (m > a[j])
- break;
- else if (m <= a[j])
- {
- a[j / 2] = a[j];
- j = 2 * j;
- }
- }
- a[j / 2] = m;
- return;
- }
- void siftDown1(int *a, int i, int n, int k)
- {
- int j, m;
- m = a[i];
- j = 2 * i;
- while (j <= n)
- {
- if (j < n && a[j + 1] < a[j])
- j = j + 1;
- if (m < a[j])
- break;
- else if (m >= a[j])
- {
- a[j / 2] = a[j];
- j = 2 * j;
- }
- }
- a[j / 2] = m;
- return;
- }
- void heapsort(int *a, int n, int k)
- {
- int i, temp;
- for (i = n; i >= n - k; i--)
- {
- temp = a[i];
- a[i] = a[1];
- a[1] = temp;
- siftDown(a, 1, i - 1, k);
- }
- }
- void heapsort1(int *a, int n, int k)
- {
- int i, temp;
- int c = k;
- for (i = n; i >= n - k; i--)
- {
- temp = a[i];
- a[i] = a[1];
- a[1] = temp;
- siftDown1(a, 1, i - 1, k);
- }
- }
- int main()
- {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n, a[10000000], k;
- cin >> n >> k;
- for (int i = 1; i <= n; i++)
- scanf("%d", &a[i]);
- if (k <= n / 2)
- {
- for (int i = n / 2; i >= 1; i--)
- siftDown(a, i, n, k);
- }
- else
- {
- for (int i = n / 2; i >= 1; i--)
- siftDown1(a, i, n, k);
- }
- if (k <= n / 2)
- {
- heapsort(a, n, k);
- printf("%d", a[n - k + 1]);
- }
- else
- {
- heapsort1(a, n, k);
- printf("%d", a[k]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement