c++ - con - Diferencia entre la cola de prioridad y un montón

cola de prioridad java

Question

Parece que una cola de prioridad es solo un montón con operaciones de cola normales como insertar, eliminar, arriba, etc. ¿Es esta la forma correcta de interpretar una cola de prioridad? Sé que puede crear colas de prioridad de diferentes maneras, pero si tuviera que crear una cola de prioridad a partir de un montón, es necesario crear una clase de cola de prioridad y dar instrucciones para construir un montón y las operaciones de la cola o si realmente no es necesario compilar ¿la clase?

Lo que quiero decir es que si tengo una función para compilar un montón y funciones para realizar operaciones como insertar, eliminar, ¿necesito poner todas estas funciones en una clase o simplemente puedo usar las instrucciones llamándolas a main ?

Supongo que mi pregunta es si tener una colección de funciones es equivalente a almacenarlas en alguna clase y usarlas a través de una clase o simplemente usar las funciones mismas.

Lo que tengo a continuación son todos los métodos para una implementación de cola de prioridad. ¿Es esto suficiente para llamarlo una implementación o debo colocarlo en una clase de cola de prioridad designada?

#ifndef MAX_PRIORITYQ_H
#define MAX_PRIORITYQ_H
#include <iostream>
#include <deque>
#include "print.h"
#include "random.h"

int parent(int i)
{
    return (i - 1) / 2;
}

int left(int i)
{
    if(i == 0)
        return 1;
    else
        return 2*i;
}

int right(int i)
{
    if(i == 0)
        return 2;
    else
        return 2*i + 1;
}

void max_heapify(std::deque<int> &A, int i, int heapsize)
{
    int largest;
    int l = left(i);
    int r = right(i);
    if(l <= heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;
    if(r <= heapsize && A[r] > A[largest])
        largest = r;
    if(largest != i) {
        exchange(A, i, largest);
        max_heapify(A, largest, heapsize);
        //int j = max_heapify(A, largest, heapsize);
        //return j;
    }
    //return i;
}

void build_max_heap(std::deque<int> &A)
{
    int heapsize = A.size() - 1;
    for(int i = (A.size() - 1) / 2; i >= 0; i--)
        max_heapify(A, i, heapsize);
}

int heap_maximum(std::deque<int> &A)
{
    return A[0];
}

int heap_extract_max(std::deque<int> &A, int heapsize)
{
    if(heapsize < 0)
        throw std::out_of_range("heap underflow");
    int max = A.front();
    //std::cout << "heapsize : " << heapsize << std::endl;
    A[0] = A[--heapsize];
    A.pop_back();
    max_heapify(A, 0, heapsize);
    //int i = max_heapify(A, 0, heapsize);
    //A.erase(A.begin() + i);
    return max;
}

void heap_increase_key(std::deque<int> &A, int i, int key)
{
    if(key < A[i])
        std::cerr << "New key is smaller than current key" << std::endl;
    else {
        A[i] = key;
        while(i > 1 && A[parent(i)] < A[i]) {
            exchange(A, i, parent(i));
            i = parent(i);
        }
    }
}

void max_heap_insert(std::deque<int> &A, int key)
{
    int heapsize =  A.size();
    A[heapsize] = std::numeric_limits<int>::min();
    heap_increase_key(A, heapsize, key);
}

Answer 1

La biblioteca de plantillas estándar de C ++ proporciona los algoritmos make_heap, push_heap y pop_heap para montones (generalmente implementados como montones binarios), que operan en iteradores de acceso aleatorio arbitrario. Trata a los iteradores como una referencia a una matriz y usa la conversión de matriz a pila. También proporciona el adaptador de contenedor con la prioridad_queue, que envuelve estas instalaciones en una clase similar a un contenedor. Sin embargo, no hay un soporte estándar para la operación de disminución / aumento de clave.

priority_queue se refiere al tipo de datos abstracto definido completamente por las operaciones que se pueden realizar en él. En C ++ STL, prioroty_queue es, por lo tanto, uno de los adaptadores de secuencia : los adaptadores de contenedores básicos (vector, list y deque son básicos porque no pueden construirse entre sí sin pérdida de eficiencia), definidos en el encabezado <queue> ( <bits/stl_queue.h> en mi caso en realidad). Como puede verse en su definición, (como dice Bjarne Stroustrup):

adaptador de contenedor proporciona una interfaz restringida a un contenedor. En particular, los adaptadores no proporcionan iteradores; Están destinados a ser utilizados únicamente a través de sus interfaces especializadas .

En mi implementación, prioroty_queue se describe como

/**
   *  @brief  A standard container automatically sorting its contents.
   *
   *  @ingroup sequences
   *
   *  This is not a true container, but an @e adaptor.  It holds
   *  another container, and provides a wrapper interface to that
   *  container.  The wrapper is what enforces priority-based sorting 
   *  and %queue behavior.  Very few of the standard container/sequence
   *  interface requirements are met (e.g., iterators).
   *
   *  The second template parameter defines the type of the underlying
   *  sequence/container.  It defaults to std::vector, but it can be
   *  any type that supports @c front(), @c push_back, @c pop_back,
   *  and random-access iterators, such as std::deque or an
   *  appropriate user-defined type.
   *
   *  The third template parameter supplies the means of making
   *  priority comparisons.  It defaults to @c less<value_type> but
   *  can be anything defining a strict weak ordering.
   *
   *  Members not found in "normal" containers are @c container_type,
   *  which is a typedef for the second Sequence parameter, and @c
   *  push, @c pop, and @c top, which are standard %queue operations.
   *  @note No equality/comparison operators are provided for
   *  %priority_queue.
   *  @note Sorting of the elements takes place as they are added to,
   *  and removed from, the %priority_queue using the
   *  %priority_queue''s member functions.  If you access the elements
   *  by other means, and change their data such that the sorting
   *  order would be different, the %priority_queue will not re-sort
   *  the elements for you.  (How could it know to do so?)

modelo:

  template<typename _Tp, typename _Sequence = vector<_Tp>,
       typename _Compare  = less<typename _Sequence::value_type> >
    class priority_queue
    {

En oposición a esto, el montón describe cómo se están recuperando y almacenando sus elementos en la memoria. Es una estructura de datos (basada en árbol) , otras son, por ejemplo, matriz, tabla hash, estructura, unión, conjunto ..., que además cumple con la propiedad de pila : todos los nodos son [mayor o igual que] o [menor que o igual a] cada uno de sus hijos, según un predicado de comparación definido para el montón.

Así que en mi cabecera de pila no encuentro ningún contenedor de pila, sino un conjunto de algoritmos

  /**
   * @defgroup heap_algorithms Heap Algorithms
   * @ingroup sorting_algorithms
   */ 

me gusta:

• __is_heap_until
• __is_heap
• __push_heap
• __adjust_heap
• __pop_heap
• make_heap
• sort_heap

todos ellos (excepto __is_heap, comentados como "Esta función es una extensión, no forma parte del estándar C ++") se describen como

   *  @ingroup heap_algorithms
   *
   *  This operation... (what it  does)

Answer 2

El término cola de prioridad se refiere a la estructura general de datos útil para ordenar las prioridades de su elemento. Hay varias formas de lograrlo, por ejemplo, varias estructuras de árboles ordenadas (por ejemplo, un árbol de distribución funciona razonablemente bien), así como varios montones, por ejemplo, d-heaps o Fibonacci heaps. Conceptualmente, un montón es una estructura de árbol donde el peso de cada nodo no es menor que el peso de cualquier nodo en el subárbol enrutado en ese nodo.

Answer 3

Realmente no. La "prioridad" en el nombre proviene de un valor de prioridad para las entradas en la cola, definiendo su ... por supuesto: prioridad. Sin embargo, hay muchas formas de implementar tal PQ.

Answer 4

Tener una clase con exactamente la interfaz que necesita (¿solo insertar y pop-max?) Tiene sus ventajas.

• Puede intercambiar la implementación (lista en lugar de montón, por ejemplo) más tarde.
• Alguien que lea el código que usa la cola no necesita entender la interfaz más difícil de la estructura de datos del montón.

Supongo que mi pregunta es si tener una colección de funciones es equivalente a almacenarlas en alguna clase y usarlas a través de una clase o simplemente usar las funciones mismas.

Es casi equivalente si solo piensa en términos de "cómo se comporta mi programa". Pero no es equivalente en términos de "qué tan fácil es que mi programa sea comprendido por un lector humano"

Answer 5

Una cola de prioridad es un tipo de datos abstracto . Es una forma abreviada de describir una interfaz y un comportamiento en particular, y no dice nada sobre la implementación subyacente.

Un montón es una estructura de datos . Es un nombre para una forma particular de almacenar datos que hace que ciertas operaciones sean muy eficientes.

Da la casualidad de que un montón es una muy buena estructura de datos para implementar una cola de prioridad, porque las operaciones que se hacen eficientes por la estructura de datos del montón son las operaciones que necesita la interfaz de la cola de prioridad.