Cola de prioridad de dos extremos

Posted on by Rudeus Greyrat

Una cola de prioridad de dos extremos admite operaciones tanto de almacenamiento dinámico máximo (una cola de prioridad máxima) como de almacenamiento dinámico mínimo (una cola de prioridad mínima). Se esperan las siguientes operaciones de la cola de prioridad doble. 
 

  1. getMax() : Devuelve el elemento máximo.
  2. getMin() : Devuelve el elemento mínimo.
  3. deleteMax() : Elimina el elemento máximo.
  4. deleteMin() : Elimina el elemento mínimo.
  5. size() : Devuelve el conteo de elementos.
  6. isEmpty() : Devuelve verdadero si la cola está vacía.

Podemos probar diferentes estructuras de datos como Lista enlazada . En el caso de una lista enlazada, si mantenemos los elementos ordenados, entonces la complejidad temporal de todas las operaciones se convierte en O(1) excepto la operación insert() que requiere tiempo O(n). 
Podemos probar dos montones (min heap y max heap). Mantenemos un puntero de cada elemento del montón máximo en el montón mínimo. Para obtener el elemento mínimo, simplemente devolvemos root. Para obtener el elemento máximo, devolvemos la raíz del montón máximo. Para insertar un elemento, lo insertamos tanto en el montón mínimo como en el montón máximo. La idea principal es mantener una correspondencia uno a uno, de modo que deleteMin() y deleteMax() se puedan realizar en tiempo O(Log n). 
 

  1. obtenerMax() : O(1)
  2. getMin() : O(1)
  3. deleteMax() : O(Iniciar sesión)
  4. deleteMin() : O(Iniciar sesión)
  5. tamaño() : O(1)
  6. estáVacío() : O(1)

Otra solución es utilizar un árbol de búsqueda binaria autoequilibrado. Se implementa un BST de autoequilibrio como se establece en C++ y TreeSet en Java .
 

  1. obtenerMax() : O(1)
  2. getMin() : O(1)
  3. deleteMax() : O(Iniciar sesión)
  4. deleteMin() : O(Iniciar sesión)
  5. tamaño() : O(1)
  6. estáVacío() : O(1)

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to implement double-ended
// priority queue using self balancing BST.
#include <bits/stdc++.h>
using namespace std;
 
struct DblEndedPQ {
    set<int> s;
 
    // Returns size of the queue. Works in
    // O(1) time
    int size()
    {
       return s.size();
    }
 
    // Returns true if queue is empty. Works
    // in O(1) time
    bool isEmpty()
    {
       return (s.size() == 0);
    }
 
    // Inserts an element. Works in O(Log n)
    // time
    void insert(int x)
    {
        s.insert(x);
    }
 
    // Returns minimum element. Works in O(1)
    // time
    int getMin()
    {
        return *(s.begin());
    }
 
    // Returns maximum element. Works in O(1)
    // time
    int getMax()
    {
        return *(s.rbegin());
    }
   
    // Deletes minimum element. Works in O(Log n)
    // time 
    void deleteMin()
    {
        if (s.size() == 0)
            return;
        s.erase(s.begin());
    }
 
    // Deletes maximum element. Works in O(Log n)
    // time 
    void deleteMax()
    {
        if (s.size() == 0)
            return;
        auto it = s.end();
        it--;
        s.erase(it);
    }
};
 
// Driver code
int main()
{
    DblEndedPQ d;
    d.insert(10);
    d.insert(50);
    d.insert(40);
    d.insert(20);
    cout << d.getMin() << endl;
    cout << d.getMax() << endl;
    d.deleteMax();
    cout << d.getMax() << endl;
    d.deleteMin();
    cout << d.getMin() << endl;
    return 0;
}

Java

// Java program to implement double-ended
// priority queue using self balancing BST.
import java.util.*;
class solution
{
 
static class DblEndedPQ {
    Set<Integer> s;
    DblEndedPQ()
    {
        s= new HashSet<Integer>();
    }
    // Returns size of the queue. Works in
    // O(1) time
    int size()
    {
    return s.size();
    }
 
    // Returns true if queue is empty. Works
    // in O(1) time
    boolean isEmpty()
    {
    return (s.size() == 0);
    }
 
    // Inserts an element. Works in O(Log n)
    // time
    void insert(int x)
    {
        s.add(x);
         
    }
 
    // Returns minimum element. Works in O(1)
    // time
    int getMin()
    {
        return Collections.min(s,null);
    }
 
    // Returns maximum element. Works in O(1)
    // time
    int getMax()
    {
        return Collections.max(s,null);
    }
     
    // Deletes minimum element. Works in O(Log n)
    // time
    void deleteMin()
    {
        if (s.size() == 0)
            return ;
        s.remove(Collections.min(s,null));
         
    }
 
    // Deletes maximum element. Works in O(Log n)
    // time
    void deleteMax()
    {
        if (s.size() == 0)
            return ;
        s.remove(Collections.max(s,null));
         
    }
};
 
// Driver code
public static void main(String args[])
{
    DblEndedPQ d= new DblEndedPQ();
    d.insert(10);
    d.insert(50);
    d.insert(40);
    d.insert(20);
    System.out.println( d.getMin() );
    System.out.println(d.getMax() );
    d.deleteMax();
    System.out.println( d.getMax() );
    d.deleteMin();
    System.out.println( d.getMin() );
}
}
//contributed by Arnab Kundu

C#

// C# program to implement double-ended
// priority queue using self balancing BST.
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG
{
 
public class DblEndedPQ
{
    HashSet<int> s;
    public DblEndedPQ()
    {
        s = new HashSet<int>();
    }
     
    // Returns size of the queue. Works in
    // O(1) time
    public int size()
    {
        return s.Count;
    }
 
    // Returns true if queue is empty. Works
    // in O(1) time
    public bool isEmpty()
    {
        return (s.Count == 0);
    }
 
    // Inserts an element. Works in O(Log n)
    // time
    public void insert(int x)
    {
        s.Add(x);
         
    }
 
    // Returns minimum element. Works in O(1)
    // time
    public int getMin()
    {
        return s.Min();
    }
 
    // Returns maximum element. Works in O(1)
    // time
    public int getMax()
    {
        return s.Max();
    }
     
    // Deletes minimum element. Works in O(Log n)
    // time
    public void deleteMin()
    {
        if (s.Count == 0)
            return ;
        s.Remove(s.Min());
         
    }
 
    // Deletes maximum element. Works in O(Log n)
    // time
    public void deleteMax()
    {
        if (s.Count == 0)
            return ;
        s.Remove(s.Max());
         
    }
};
 
// Driver code
public static void Main(String[] args)
{
    DblEndedPQ d= new DblEndedPQ();
    d.insert(10);
    d.insert(50);
    d.insert(40);
    d.insert(20);
    Console.WriteLine( d.getMin() );
    Console.WriteLine(d.getMax() );
    d.deleteMax();
    Console.WriteLine( d.getMax() );
    d.deleteMin();
    Console.WriteLine( d.getMin() );
}
}
 
// This code contributed by Rajput-Ji

Javascript

<script>
      // JavaScript program to implement double-ended
      // priority queue using self balancing BST.
      class DblEndedPQ {
        constructor() {
          this.s = new Set();
        }
 
        // Returns size of the queue. Works in
        // O(1) time
        size() {
          return this.s.size;
        }
 
        // Returns true if queue is empty. Works
        // in O(1) time
        isEmpty() {
          return this.s.size == 0;
        }
 
        // Inserts an element. Works in O(Log n)
        // time
        insert(x) {
          this.s.add(x);
        }
 
        // Returns minimum element. Works in O(1)
        // time
        getMin() {
          return Math.min(...Array.from(this.s.values()));
        }
 
        // Returns maximum element. Works in O(1)
        // time
        getMax() {
          return Math.max(...Array.from(this.s.values()));
        }
 
        // Deletes minimum element. Works in O(Log n)
        // time
        deleteMin() {
          if (this.s.size == 0) return;
          this.s.delete(this.getMin());
        }
 
        // Deletes maximum element. Works in O(Log n)
        // time
        deleteMax() {
          if (this.s.size == 0) return;
          this.s.delete(this.getMax());
        }
      }
 
      // Driver code
      var d = new DblEndedPQ();
      d.insert(10);
      d.insert(50);
      d.insert(40);
      d.insert(20);
      document.write(d.getMin() + "<br>");
      document.write(d.getMax() + "<br>");
      d.deleteMax();
      document.write(d.getMax() + "<br>");
      d.deleteMin();
      document.write(d.getMin() + "<br>");
       
      // This code is contributed by rdtank.
    </script>
Producción: 

10
50
40
20

 

Comparación de soluciones Heap y BST La solución 
basada en heap requiere O(n) espacio adicional para un montón adicional. La solución basada en BST no requiere espacio adicional. La ventaja de la solución basada en montón es que admite caché.
 

Publicación traducida automáticamente

Artículo escrito por kartik 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 *