Package br.unip.aps.estruturas

Class HeapBinario<T>

java.lang.Object

br.unip.aps.estruturas.HeapBinario<T>

public final class HeapBinario<T>
extends Object

Heap binario minimo em vetor (fila de prioridade): o topo e o menor elemento segundo o comparador.

Constructor Summary

Constructors

Constructor	Description
HeapBinario(int capacidade, Comparator<? super T> comparador, OperationCounter contador)
HeapBinario(Comparator<? super T> comparador, OperationCounter contador)

Method Summary

Modifier and Type	Method	Description
void	inserir(T x)
T	removerTopo()
void	substituirTopo(T x)	Troca o topo por x e reorganiza: uma unica descida, mais barato que remover e inserir.
int	tamanho()
static <T> List<T>	topK(Iterable<T> itens, int k, Comparator<? super T> comparador, OperationCounter contador)	Os k maiores itens em ordem decrescente, mantendo um heap minimo de tamanho k: O(n log k).
T	topo()
boolean	vazio()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

HeapBinario

public HeapBinario(Comparator<? super T> comparador,
 OperationCounter contador)

HeapBinario

public HeapBinario(int capacidade,
 Comparator<? super T> comparador,
 OperationCounter contador)

Method Details

inserir

public void inserir(T x)

topo

public T topo()

removerTopo

public T removerTopo()

substituirTopo

public void substituirTopo(T x)

Troca o topo por x e reorganiza: uma unica descida, mais barato que remover e inserir.

tamanho

public int tamanho()

vazio

public boolean vazio()

topK

public static <T> List<T> topK(Iterable<T> itens,
 int k,
 Comparator<? super T> comparador,
 OperationCounter contador)

Os k maiores itens em ordem decrescente, mantendo um heap minimo de tamanho k: O(n log k).