Obtenir Min/Max en O(1) le temps d'une File d'attente?

Il existe une telle structure qui agit comme une file d'attente, mais vous permet d'extraire des min/max de la valeur de la constante de temps, en fait pas strictement constante, il est amorti de la constante de temps (nommé min/max de la file d'attente comme vous avez pu le deviner). Il y a deux façons de la mettre en œuvre - à l'aide de deux piles ou à l'aide d'une file d'attente et un deque.

Deque la mise en œuvre ressemble plus ou moins comme ceci (langue agnostique):

nous avons donc une deque maximum d'éléments, l'un sur le front de l'est souhaité max, et une file d'attente standard.

Opération Push

1. Si la file d'attente est vide, il suffit d'appuyer sur l'élément à la fois, la file d'attente et le deque.
2. Si la file d'attente n'est pas vide, pousser l'élément dans la file d'attente, en allant de l'arrière de la deque supprimer tous les éléments qui sont strictement inférieur à celui que nous sommes en train de pousser (ils vont sûrement pas être le max, car la poussée de l'élément est plus grande et le dernier dans la file d'attente pour plus de temps) et pousser l'élément courant à l'arrière de la deque

Opération de suppression

1. Si le front de la deque est égale à l'avant de la file d'attente puis de la pop à la fois (deque à partir de l'avant)
2. Si le front de la deque n'est pas égal à l'avant de la file d'attente puis de la pop juste la file d'attente, le poped élément est sûrement pas le plus important.

Obtenir un max

1. C'est juste le premier élément de la deque.

(beaucoup d'arguments doit être ajoutée pour préciser pourquoi cela fonctionne, mais la deuxième version présentée ci-dessous peut être la réponse à cette nécessité)

La Pile de la mise en œuvre est assez similaire, je pense que c'est peut être un peu plus longue à mettre en œuvre, mais peut-être plus facile à saisir. La première chose à noter est qu'il est facile à stocker le maximum de l'élément de la pile - exercice facile (pour les paresseux - Pile à trouver min/trouver-max plus efficace que O(n)?). La deuxième partie, peut-être un peu délicat si vu la première fois, c'est assez facile à mettre en place une file d'attente à l'aide de deux piles, il peut être trouvé ici - Comment mettre en place une file d'attente à l'aide de deux piles? . Et c'est, fondamentalement, il s' - si nous pouvons obtenir le maximum de l'élément à la fois des piles, nous pouvons obtenir le maximum d'élément de l'ensemble de la file d'attente (prise maximale est associatif ou quelque chose comme ça si vous voulez plus d'argument formel, mais je parie que vous n'avez pas, il est vraiment évident).

Min versions se fait de manière analogue.

Tout ce qui peut également être effectuée à l'aide d'un ensemble (ou quelque chose du genre) en O(nlogn) de temps, mais c'est inutile, car la constante en O(n) est vraiment petit et il devrait être beaucoup plus rapide, mais facile à mettre en œuvre.

NON-parties INTÉRESSANTES de la première version:

Espère que j'ai aidé un peu. Et de l'espoir qui n'a pas dit quelque chose de mal. Peut donner une mise en œuvre simple en C++/C si nécessaire. Serais reconnaissant pour toute remarque sur la forme comme c'est mon premier post de ce type n'importe où 🙂 (et l'anglais n'est pas ma langue maternelle). Aussi la confirmation de l'exactitude serait génial.

EDIT: comme cette réponse m'a certains moments, j'ai senti obligé de le nettoyer un peu, de l'étendre un peu.

OriginalL'auteur Szymon

Je voudrais stocker deux champs minIndex et maxIndex qui va stocker les positions d'index dans votre structure de données pour la valeur minimum et maximum respectivement.

Lorsque de nouveaux éléments sont ajoutés à la file d'attente, vérifier deux choses:

1. L'élément est moins que le minimum actuel de l'élément à la minIndex position; si donc mettre à jour la valeur de minIndex après l'insertion.
2. L'élément est plus grand que le courant maximum de l'élément à la maxIndex position et de mettre à jour la référence en conséquence.

Cela vous donnera un O(1) asymptote pour le courant min et la valeur max.

OriginalL'auteur algolicious

Je vous poste le code complet ici pour trouver des MIN et MAX dans la file d'attente en un temps constant.
Sentez-vous svp libre pour me contacter si vous avez un doute.

File d'attente

//Queue Interface
package com.java.util.collection.advance.datastructure.queue;
public interface Queue<E>{
    boolean addR(E e);
    E removeL();
    E element();
    E elementR();
    boolean isFull();
    boolean isEmpty();
    void trim();
}

Deque

package com.java.util.collection.advance.datastructure.queue;
/**
* A deque is a double-ended queue. You can insert items at either end and delete them
* from either end. The methods might be called insertLeft() and insertRight(), and 
* removeLeft() and removeRight().
* @author vsinha
*
* @param <E>
*/
public interface DeQueue<E> extends Queue<E>{

    boolean addL(E element);

    E removeR();

}

FindMinMaxQueue

package com.java.util.collection.advance.datastructure.queue;


@SuppressWarnings("hiding")
public interface FindMinMaxQueue<Integer> extends Queue<Integer>{

    public Integer min();

    public Integer max();
}

MyQueue

package com.java.util.collection.advance.datastructure.queue;
import java.util.Arrays;
public class MyQueue<E> implements Queue<E>,DeQueue<E>{
protected int front = 0;
protected int rear =-1;
protected E[] elements =null;
private static final int DEFAULT_INTIAL_CAPACITY =100; 
private int size =0;
public MyQueue(){
this(DEFAULT_INTIAL_CAPACITY);
}
@SuppressWarnings("unchecked")
public MyQueue(int intialCapacity){
if(intialCapacity < 0){
throw new IllegalArgumentException("intial capacity can't be null");
}
elements =(E[]) new Object[intialCapacity];
}
@Override
public boolean addR(E e) {
if(! isFull()) {
elements[++rear] = e;
size++;
return true;
}
return false;
}
@Override
public E removeL() {
E element =null;
if(!isEmpty()){
element=elements[front];
//Nullify the reference
elements[front] =null;
++front;
--size;
}
return element;
}
@Override
public E element() {
E element =null;
if(!isEmpty()){
element=elements[front];
}
return element;
}
@Override
public E elementR() {
E element =null;
if(!isEmpty()){
element=elements[rear];
}
return element;
}
public boolean isFull() {
return rear == elements.length;
}
public boolean isEmpty() {
return size == 0;
}
Override
public String toString() {
return "MyQueue [front=" + front + ", rear=" + rear + ", elements="
+ Arrays.toString(elements) + ", size=" + size + "]";
}
@Override
public void trim() {
@SuppressWarnings("unchecked")
E[] dest =(E[]) new Object[size];
System.arraycopy(elements, front, dest, 0, size);
elements = dest;
front =0;
rear=size-1;
}
@Override
public boolean addL(E element) {
if(front != 0) {
elements[--front] = element;
size++;
return true;
}
return false;
}
@Override
public E removeR() {
E element =null;
if(size > 0) {
element=elements[rear];
//Nullify the reference
elements[rear] =null;
--rear;
--size;
}
return element;
}
}

MinAndMaxFinderQueue

package com.java.util.collection.advance.datastructure.queue;
public class MinAndMaxFinderQueue extends MyQueue<Integer> implements FindMinMaxQueue<Integer> {
private Queue<Integer> maxValuesQueue =null;
private Queue<Integer> minValuesQueue =null;
public MinAndMaxFinderQueue (int intialCapacity){
super(intialCapacity);
maxValuesQueue =new MyQueue<Integer>(intialCapacity);
minValuesQueue =new MyQueue<Integer>(intialCapacity);
}
@Override
public boolean addR(Integer e) {
if(super.addR(e)){
if(max() == null || max() <= e){
maxValuesQueue.addR(e);
}
if(min() == null || min() >= e){
minValuesQueue.addR(e);
}
return true;
}
return false;
}
@Override
public Integer removeL() {
Integer element =super.removeL();
if(element !=null){
if(maxValuesQueue.element() == element){
maxValuesQueue.removeL();
}
if(minValuesQueue.element() == element){
minValuesQueue.removeL();
}
}
//Need to re-generate MIN and MAX queue when the main queue is not empty and min/max queue is empty
regenerateMin();
regenerateMax();
return element;
}
private void regenerateMin(){
Integer current =null;
if(!super.isEmpty() && min() ==null){
for(int front = super.front; front<= super.rear;front++){
current = (Integer)elements[front];
if(min() == null || min() >= current){
minValuesQueue.addR(current);
}
}
}
}
private void regenerateMax(){
Integer current =null;
if(!super.isEmpty() && max() ==null){
for(int front = super.front; front<= super.rear;front++){
current = (Integer)elements[front];
if(max() == null || max() <= current){
maxValuesQueue.addR(current);
}
}
}
}
public Integer min() {
return minValuesQueue.elementR();
}
public Integer max() {
return maxValuesQueue.elementR();
}
@Override
public String toString() {
return super.toString()+"\nMinAndMaxFinderQueue [maxValuesQueue=" + maxValuesQueue
+ ", minValuesQueue=" + minValuesQueue + "]";
}
}

Test

//Test class 
package com.java.util.collection.advance.datastructure.queue;
import java.util.Random;
public class MinMaxQueueFinderApp {
public static void main(String[] args) {
FindMinMaxQueue<Integer> queue =new MinAndMaxFinderQueue(10);
Random random =new Random();
for(int i =0; i< 10; i++){
queue.addR(random.nextInt(100));
System.out.println(queue);
System.out.println("MAX :"+queue.max());
System.out.println("MIN :"+queue.min());
}
System.out.println(queue);
System.out.println("MAX :"+queue.max());
System.out.println("MIN :"+queue.min());
queue.removeL();
System.out.println(queue);
System.out.println("MAX :"+queue.max());
System.out.println("MIN :"+queue.min());
queue.removeL();
System.out.println(queue);
System.out.println("MAX :"+queue.max());
System.out.println("MIN :"+queue.min());
queue.removeL();
System.out.println(queue);
System.out.println("MAX :"+queue.max());
System.out.println("MIN :"+queue.min());
queue.removeL();
System.out.println(queue);
System.out.println("MAX :"+queue.max());
System.out.println("MIN :"+queue.min());
queue.removeL();
System.out.println(queue);
System.out.println("MAX :"+queue.max());
System.out.println("MIN :"+queue.min());
System.out.println(queue);
System.out.println("MAX :"+queue.max());
System.out.println("MIN :"+queue.min());
}
}

OriginalL'auteur java baby