Comprender cómo crear un montón en Python

Question

La función collections.Count.most_common en Python usa el módulo heapq para devolver el recuento de la palabra más común en un archivo, por ejemplo.

He rastreado el archivo heapq.py, pero estoy teniendo problemas para entender cómo se crea/actualiza un montón con respecto a las palabras, digamos.

Por lo tanto, creo que la mejor manera de entenderlo es descubrir cómo crear un montón desde cero.

¿Alguien puede proporcionar un pseudocódigo para crear un montón que represente el conteo de palabras?

Answer 1

Ésta es una versión ligeramente modificada del código que se encuentra aquí: http://code.activestate.com/recipes/577086-heap-sort/

def HeapSort(A,T): 
    def heapify(A): 
     start = (len(A) - 2)/2 
     while start >= 0: 
      siftDown(A, start, len(A) - 1) 
      start -= 1 

    def siftDown(A, start, end): 
     root = start 
     while root * 2 + 1 <= end: 
      child = root * 2 + 1 
      if child + 1 <= end and T.count(A[child]) < T.count(A[child + 1]): 
       child += 1 
      if child <= end and T.count(A[root]) < T.count(A[child]): 
       A[root], A[child] = A[child], A[root] 
       root = child 
      else: 
       return 

    heapify(A) 
    end = len(A) - 1 
    while end > 0: 
     A[end], A[0] = A[0], A[end] 
     siftDown(A, 0, end - 1) 
     end -= 1 


if __name__ == '__main__': 
    text = "the quick brown fox jumped over the the quick brown quick log log" 
    heap = list(set(text.split())) 
    print heap 

    HeapSort(heap,text) 
    print heap 

salida

['brown', 'log', 'jumped', 'over', 'fox', 'quick', 'the'] 
['jumped', 'fox', 'over', 'brown', 'log', 'the', 'quick'] 

se puede visualizar el programa aquí http://goo.gl/2a9Bh

Answer 2

En Python 2.xy 3.x, montones son compatibles a través de una biblioteca importable, heapq. Proporciona numerosas funciones para trabajar con la estructura de datos del montón modelada en una lista de Python. Ejemplo:

>>> from heapq import heappush, heappop 
>>> heap = [] 
>>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0] 
>>> for item in data: 
     heappush(heap, item) 

>>> ordered = [] 
>>> while heap: 
     ordered.append(heappop(heap)) 

>>> ordered 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 
>>> data.sort() 
>>> data == ordered 
True 

Usted puede encontrar más información acerca de las funciones del montón: heappush, heappop, heappushpop, heapify, heapreplace en heap python docs.

Answer 3

Así es otra variación sobre la base de Sedgewick

El montón está representado internamente en una matriz en donde si un nodo está en k, es niños están en 2 * k y 2 * k + 1. El primer elemento de la matriz no se usa, para hacer que las matemáticas sean más convenientes.

Para agregar un nuevo elemento al montón, lo agrega al final de la matriz y luego llama a nadar repetidamente hasta que el nuevo elemento encuentre su lugar en el montón.

Para eliminar la raíz, la puede cambiar por el último elemento de la matriz, eliminarla y luego llamar al receptor hasta que el elemento intercambiado encuentre su lugar.

swim(k): 
    while k > 1 and less(k/2, k): 
    exch(k, k/2) 
    k = k/2 

sink(k): 
    while 2*k <= N: 
    j = 2*k 
    if j < N and less(j, j+1): 
     j++ 
    if not less(k, j): 
     break 
    exch(k, j) 
    k = j 

Aquí es una visualización de inserción montón, la inserción de las primeras 15 letras del alfabeto: [AO]