Em muitas discussões sobre heap binário, normalmente apenas a tecla de diminuição é listada como operação suportada para um min-heap. Por exemplo, o capítulo 6.1 do CLR e esta página da Wikipedia . Por que a chave de aumento normalmente não está listada para min-heap? Imagino que seja possível fazer isso em O (altura) trocando iterativamente o elemento aumentado (x) pelo mínimo de seus filhos, até que nenhum deles seja maior que x.
por exemplo
IncreaseKey(int pos, int newValue)
{
heap[pos] = newValue;
while(left(pos) < heap.Length)
{
int smallest = left(pos);
if(heap[right(pos)] < heap[left(pos)])
smallest = right(pos);
if(heap[pos] < heap[smallest])
{
swap(smallest, pos);
pos= smallest;
}
else return;
}
}
O acima está correto? Se não, por que? Se sim, por que a chave de aumento não está listada para min-heap?
algorithms
data-structures
heaps
priority-queues
GatotPujo
fonte
fonte
Respostas:
O algoritmo que você sugere é simplesmente heapify. E, de fato - se você aumentar o valor de um elemento em um min-heap e, em seguida, amontoar sua subárvore, você terminará com um min-heap legal.
fonte
A razão pela qual sua operação não está listada é que uma não está simplesmente interessada em todas as operações que podem ser facilmente implementadas usando uma determinada estrutura de dados, mas na outra maneira. Dado um conjunto de operações, qual é a maneira mais eficiente (em termos de espaço e tempo) de implementar essas operações. (Mas eu adiciono mais a isso depois)
Montes binários implementam a fila de prioridade da estrutura de dados abstratos, que solicita operações is_empty, add_element (uma chave com sua prioridade), find_min e delete_min. Filas mais avançadas também permitem diminuir a prioridade da chave (em um min_heap) ou até aumentá-la. De fato, você deu uma implementação.
Duas observações. Sua operação é usada na função heapify, que constrói eficientemente um heap a partir de uma matriz. No heapify, sua operação é repetida (a partir da última tecla).
Então, o mais importante, seu código usa a posição do nó. Para a fila de prioridade pura da estrutura de dados que está trapaceando. Essa estrutura de dados pede para executar uma certa operação dada uma chave. Portanto, para diminuir ou aumentar a prioridade de um elemento, você primeiro precisará localizá-lo. Eu acho que é a principal razão pela qual não está listado.
fonte
Penso que a primeira coisa a considerar é o que é uma operação suportada?
"Inserir um valor com uma chave fixa específica" (por exemplo, para chaves obtidas da região inteira, inserindo com a chave = 3) corresponde a uma operação suportada para a pilha mínima?
Não, porque essa operação pode ser implementada trivialmente com operações suportadas mais gerais. Da mesma forma, a inserção de 2 elementos de uma só vez pode ser feita com a
insertoperação existente .Por outro lado, a
insertoperação não pode ser definida senão expondo os detalhes da implementação. É praticamente o mesmo para as operações listadas na página da Wikipedia,heapifyexceto, que provavelmente poderiam ser implementadas por uma sequência deinsert.Em outras palavras, existem operações elementares fornecidas no tipo, que estão fortemente vinculadas aos detalhes da implementação para que elas tenham um bom desempenho, e há outras operações que não cumprem essa regra e, portanto, podem ser implementadas como combinações dos canônicos.
Com essa definição em mente, você acha que a chave de aumento pode ser implementada com outras operações suportadas exclusivamente, sem perda de desempenho? Nesse caso, não é uma operação suportada pela definição acima; caso contrário, você pode estar certo.
Indiscutivelmente, a definição de uma operação suportada que forneço é minha, até onde eu sei. Não é formal e, portanto, sujeito a discussão (embora me pareça bastante claro). No entanto, eu ficaria feliz se alguém pudesse fornecer uma fonte que defina clara e inequivocamente o que é uma operação suportada para tipos de dados ou, pelo menos, defina-a em termos melhores que os meus (essa definição é dada no CLR? Não tenho uma cópia )
Meu segundo ponto será sobre como definimos uma fila de prioridade (que é a razão de ser dos heaps binários). A
increase_keyoperação é necessária para esse tipo de dados, ou seja, para seu uso adequado?Como você pode ver, meu ângulo é sobre definições. Na verdade, eu não respondo suas perguntas, apenas alguns indicadores; portanto, as melhorias são bem-vindas.
fonte