inicio GeNeura cursos

Algorimos de heap


Un heap es una especie de árbol binario representado sobre una estructura lineal como un vector o deque. Son fácilmente ordenables y son muy utilizados en gran cantidad de algoritmos como el heapsort. Dentro de un heap se puede facilmente establecer una relación de orden, de tal forma que para todo elemento que ocupe la posición i, los elementos 2*i+1 y 2*i+2 será menores (o mayores, según nos interese).

Lista de algoritmos de heap


push_heap()

Función

template <class RandomAccessIterator, class Compare>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last,
                      Compare comp)

Descripción

push_heap() introduce un elemento dentro de un heap y deja el heap ordenado de una forma muy eficiente.


pop_heap()

Función

template <class RandomAccessIterator, class Compare>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp)

Descripción

pop_heap() elimina el maximo elemento de un heap y deja la estructura ordenada de nuevo.


make_heap()

Función

template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last)

template <class RandomAccessIterator, class Compare>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last,
                      Compare comp)

Descripción

make_heap() crea un heap a partir de una secuencia de elementos desordenada.


sort_heap()

Función

template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
  while (last - first > 1) pop_heap(first, last--);
}

template <class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
               Compare comp) {
  while (last - first > 1) pop_heap(first, last--, comp);
}

Descripción

sort_heap() este algoritmo toma como entrada una secuencia de datos que represente un heap y devuelve una secuencia ordenada.