K’ésimo Elemento Mínimo en un Min-Heap

Dado un montón mínimo de tamaño n, encuentre el k -ésimo elemento mínimo en el montón mínimo.

Ejemplos:

Entrada : {10, 50, 40, 75, 60, 65, 45}
k = 4
Salida : 50

Entrada : {10, 50, 40, 75, 60, 65, 45}
k = 2
Salida : 40

Enfoque ingenuo :
podemos extraer el elemento mínimo del montón mínimo k veces y el último elemento extraído será el k -ésimo elemento mínimo. 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).

// C++ program to find k-th smallest
// element in Min Heap.
#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 minimum element
int extractMin(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 findKthSmalles(Heap &h, int k)
{
    for (int i = 1; i < k; ++i)
        extractMin(h);
    return extractMin(h);
}
  
int main()
{
    Heap h(7);
    h.v = vector<int>{ 10, 50, 40, 75, 60, 65, 45 };
    int k = 2;
    cout << findKthSmalles(h, k);
    return 0;
}
Producción:

40

Complejidad de tiempo: O(k * log n)

Enfoque eficiente :
podemos notar una observación interesante sobre min-heap. Un elemento x en el i -ésimo nivel tiene i – 1 ancestros. Por la propiedad de min-heaps, se garantiza que estos ancestros i – 1 son menores que x. Esto implica que x no puede estar entre los menos i – 1 elementos del montón. Usando esta propiedad, podemos concluir que el k -ésimo elemento mínimo puede tener un nivel de k como máximo.

Podemos reducir el tamaño del montón mínimo de modo que solo tenga k niveles. Entonces podemos obtener el k -ésimo elemento mínimo mediante nuestra estrategia anterior de extraer el elemento mínimo 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 almacenamiento en montón llevará un tiempo O(log 2 k ) = O(k). La complejidad temporal total será O(k 2 ). Si n >> k, entonces este enfoque funciona mejor que el anterior.

// C++ program to find k-th smallest
// element in Min Heap using k levels
#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 minimum element
int extractMin(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 findKthSmalles(Heap &h, int k)
{
    h.n = min(h.n, int(pow(2, k) - 1));
    for (int i = 1; i < k; ++i)
        extractMin(h);
    return extractMin(h);
}
  
int main()
{
    Heap h(7);
    h.v = vector<int>{ 10, 50, 40, 75, 60, 65, 45 };
    int k = 2;
    cout << findKthSmalles(h, k);
    return 0;
}
Producción:

40

Complejidad de tiempo: O(k 2 )

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 (o Min Heap) e inserte el Node raíz del min-heap en P. La función de comparación de la cola de prioridad debe ser tal que se extraiga el elemento mínimo.
  2. Repita estos pasos k – 1 veces:
    1. Extraiga el elemento mínimo de P.
    2. Inserte los elementos secundarios izquierdo y derecho del elemento emergente. (si existen).
  3. El elemento mínimo en P es el k -ésimo elemento mínimo del montón mínimo.

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).

// C++ program to find k-th smallest
// element in Min Heap using another
// Min Heap (Or Priority Queue)
#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 findKthSmalles(Heap &h, int k)
{
    // Create a Priority Queue
    priority_queue<pair<int, int>,
                   vector<pair<int, int> >,
                   greater<pair<int, int> > >
        p;
  
    // Insert root into the priority queue
    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;
}
  
int main()
{
    Heap h(7);
    h.v = vector<int>{ 10, 50, 40, 75, 60, 65, 45 };
    int k = 4;
    cout << findKthSmalles(h, k);
    return 0;
}
Producción:

50

Complejidad temporal: O(k * log k)

Publicación traducida automáticamente

Artículo escrito por vaibhav29498 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *