K-ésimo elemento más grande en un Max-Heap

Dado un montón máximo de tamaño n, encuentre el k ^-ésimo elemento más grande en el montón máximo. Ejemplos:

Entrada : maxHeap = {20, 15, 18, 8, 10, 5, 17} k = 4 Salida : 15 Entrada : maxHeap = {100, 50, 80, 10, 25, 20, 75} k = 2 Salida : 80

Enfoque ingenuo : podemos extraer el elemento máximo del montón máximo k veces y el último elemento extraído será el k ^-ésimo elemento más grande. Cada operación de eliminación requiere un tiempo O(log n), por lo que la complejidad temporal total de este enfoque resulta ser O(k * log n). A continuación se muestra la implementación de este enfoque: 

// C++ program for the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure for the heap
struct Heap {
 vector<int> v;
 int n; // Size of the heap
 
 Heap(int i = 0)
  : n(i)
 {
  v = vector<int>(n);
 }
};
 
// Generic function to
// swap two integers
void swap(int& a, int& b)
{
 int temp = a;
 a = b;
 b = temp;
}
 
// Returns the index of
// the parent node
inline int parent(int i)
{
 return (i - 1) / 2;
}
 
// Returns the index of
// the left child node
inline int left(int i)
{
 return 2 * i + 1;
}
 
// Returns the index of
// the right child node
inline int right(int i)
{
 return 2 * i + 2;
}
 
// Maintains the heap property
void heapify(Heap& h, int i)
{
 int l = left(i), r = right(i), m = i;
 if (l < h.n && h.v[i] < h.v[l])
  m = l;
 if (r < h.n && h.v[m] < h.v[r])
  m = r;
 if (m != i) {
  swap(h.v[m], h.v[i]);
  heapify(h, m);
 }
}
 
// Extracts the maximum element
int extractMax(Heap& h)
{
 if (!h.n)
  return -1;
 int m = h.v[0];
 h.v[0] = h.v[h.n-- - 1];
 heapify(h, 0);
 return m;
}
 
int kThGreatest(Heap &h, int k)
{
 for (int i = 1; i < k; ++i)
  extractMax(h);
 return extractMax(h);
}
 
// Driver Code
int main()
{
 Heap h(7);
 h.v = vector<int>{ 20, 15, 18, 8, 10, 5, 17 };
 int k = 4;
 
 cout << kThGreatest(h, k);
 return 0;
}

15

Complejidad de tiempo : O(k * log n) 

Espacio Auxiliar: O(n)

Enfoque eficiente : podemos notar una observación interesante sobre max-heap. Un elemento x en el i ^-ésimo nivel tiene i – 1 ancestros. Por la propiedad de max-heaps, se garantiza que estos ancestros i – 1 son mayores que x. Esto implica que x no puede estar entre los mayores i – 1 elementos del montón. Usando esta propiedad, podemos concluir que el k ^-ésimo elemento más grande puede tener un nivel de k como máximo. Podemos reducir el tamaño del montón máximo de modo que solo tenga k niveles. Entonces podemos obtener el k ^-ésimo elemento más grande por nuestra estrategia anterior de extraer el elemento máximo k veces. Tenga en cuenta que el tamaño del montón se reduce a un máximo de 2 ^k– 1, por lo que cada operación de heapificación tomará un tiempo O(log 2 ^k ) = O(k). La complejidad temporal total será O(k ² ). Si n >> k, entonces este enfoque funciona mejor que el anterior. A continuación se muestra la implementación de este enfoque: 

// C++ program for the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure for the heap
struct Heap {
 vector<int> v;
 int n; // Size of the heap
 
 Heap(int i = 0)
  : n(i)
 {
  v = vector<int>(n);
 }
};
 
// Generic function to
// swap two integers
void swap(int& a, int& b)
{
 int temp = a;
 a = b;
 b = temp;
}
 
// Returns the index of
// the parent node
inline int parent(int i)
{
 return (i - 1) / 2;
}
 
// Returns the index of
// the left child node
inline int left(int i)
{
 return 2 * i + 1;
}
 
// Returns the index of
// the right child node
inline int right(int i)
{
 return 2 * i + 2;
}
 
// Maintains the heap property
void heapify(Heap& h, int i)
{
 int l = left(i), r = right(i), m = i;
 if (l < h.n && h.v[i] < h.v[l])
  m = l;
 if (r < h.n && h.v[m] < h.v[r])
  m = r;
 if (m != i) {
  swap(h.v[m], h.v[i]);
  heapify(h, m);
 }
}
 
// Extracts the maximum element
int extractMax(Heap& h)
{
 if (!h.n)
  return -1;
 int m = h.v[0];
 h.v[0] = h.v[h.n-- - 1];
 heapify(h, 0);
 return m;
}
 
int kThGreatest(Heap &h, int k)
{
 // Change size of heap
 h.n = min(h.n, int(pow(2, k) - 1));
 
 for (int i = 1; i < k; ++i)
  extractMax(h);
 
 return extractMax(h);
}
 
// Driver Code
int main()
{
 Heap h(7);
 h.v = vector<int>{ 20, 15, 18, 8, 10, 5, 17 };
 int k = 2;
 
 cout << kThGreatest(h, k);
 return 0;
}

18

Complejidad de tiempo : O(k ² ) 

Espacio Auxiliar: O(n)

Enfoque más eficiente : podemos mejorar aún más la complejidad temporal de este problema mediante el siguiente algoritmo:

1. Cree una cola de prioridad P e inserte el Node raíz del montón máximo en P.
2. Repita estos pasos k – 1 veces:
   1. Pop el mayor elemento de P.
   2. Inserte los elementos secundarios izquierdo y derecho del elemento emergente. (si existen).
3. El elemento más grande en P es el k ^-ésimo elemento más grande del montón máximo.

El tamaño inicial de la cola de prioridad es uno, y aumenta como máximo en uno en cada uno de los k – 1 pasos. Por lo tanto, hay un máximo de k elementos en la cola de prioridad y la complejidad temporal de las operaciones de extracción e inserción es O(log k). Por tanto, la complejidad temporal total es O(k * log k). A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure for the heap
struct Heap {
 vector<int> v;
 int n; // Size of the heap
 
 Heap(int i = 0)
  : n(i)
 {
  v = vector<int>(n);
 }
};
 
// Returns the index of
// the left child node
inline int left(int i)
{
 return 2 * i + 1;
}
 
// Returns the index of
// the right child node
inline int right(int i)
{
 return 2 * i + 2;
}
 
int kThGreatest(Heap &h, int k)
{
 priority_queue<pair<int, int> > p;
 p.push(make_pair(h.v[0], 0));
 
 for (int i = 0; i < k - 1; ++i) {
  int j = p.top().second;
  p.pop();
  int l = left(j), r = right(j);
  if (l < h.n)
   p.push(make_pair(h.v[l], l));
  if (r < h.n)
   p.push(make_pair(h.v[r], r));
 }
 return p.top().first;
}
 
// Driver Code
int main()
{
 Heap h(7);
 h.v = vector<int>{ 20, 15, 18, 8, 10, 5, 17 };
 int k = 2;
 
 cout << kThGreatest(h, k);
 return 0;
}

18

Complejidad del tiempo : O(N * log k)

Espacio Auxiliar: O(n)

Para cada elemento, insertamos el elemento en el montón y lo eliminamos si el tamaño del montón es mayor que k. Por lo tanto, se requerirá precisamente 1 operación de pila para los k elementos iniciales y luego se requerirán 2 operaciones de pila para el resto de los elementos. Esto hace que la complejidad del tiempo sea O(N*logK)