Introduction détaillée au tas binaire en python (exemple de code)

Cet article vous apporte une introduction détaillée (exemple de code) sur le tas binaire en python. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

1. Heap

Structure des données Le tas est une file d'attente prioritaire. Une file d'attente est une structure de données premier entré, premier sorti. Une variante importante de la file d'attente est appelée file d'attente prioritaire. L'utilisation de la file d'attente prioritaire peut ajouter des objets dans n'importe quel ordre et trouver (ou éventuellement supprimer) le plus petit élément à tout moment (éventuellement lors de l'ajout d'objets), ce qui signifie qu'elle est plus efficace que la méthode min de Python.
Dans une file d'attente prioritaire, l'ordre logique des éléments dans la file d'attente est déterminé par leur priorité. L'élément de priorité la plus élevée se trouve au début de la file d'attente et l'élément de priorité la plus basse se trouve à la fin. Ainsi, lorsque vous placez des éléments dans la file d’attente prioritaire, les nouveaux éléments peuvent continuer à passer au premier plan.

2. Opérations sur le tas binaire

Les opérations de base de notre implémentation du tas binaire sont les suivantes :

BinaryHeap() crée un nouveau binaire vide. tas.
insert(k) ajoute un nouvel élément au tas.
findMin() renvoie l'élément avec la plus petite valeur clé et laisse l'élément dans le tas.
delMin() Renvoie l'élément avec la plus petite valeur de clé, supprimant l'élément du tas.
Si le tas est vide, isEmpty() renvoie true, sinon il renvoie false.
size() renvoie le nombre d'éléments dans le tas.
buildHeap(list) Construit un nouveau tas à partir d'une liste de clés.

Notez que quel que soit l'ordre dans lequel nous ajoutons des éléments au tas, le plus petit est supprimé à chaque fois.

Pour que notre tas fonctionne efficacement, nous profiterons de la nature logarithmique des arbres binaires pour représenter notre tas. Pour garantir des performances logarithmiques, nous devons maintenir l’arbre équilibré. Arbre binaire équilibré a approximativement le même nombre de nœuds dans les sous-arbres gauche et droit de la racine, c'est un arbre vide ou la valeur absolue de la différence de hauteur entre ses sous-arbres gauche et droit ne dépasse pas 1, et les sous-arbres gauche et droit. Les sous-arbres sont tous des arbres binaires équilibrés. Dans notre implémentation du tas, nous maintenons l'équilibre de l'arbre en créant un arbre binaire complet. Un arbre binaire complet est un arbre dans lequel les nœuds de chaque niveau sont complètement remplis, et si le dernier niveau n'est pas plein, alors seuls quelques nœuds de droite manquent. La figure 1 montre un exemple d'arbre binaire complet.
Une autre propriété intéressante d'un arbre binaire complet est que l'on peut le représenter à l'aide d'une seule liste.

# from pythonds.trees.binheap import BinHeap
class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0
    def insert(self,k):
        '''将项附加到列表的末尾，并通过比较新添加的项与其父项，我们可以重新获得堆结构属性。 '''
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)
    def buildHeap(self, alist):
        '''直接将整个列表生成堆，将总开销控制在O(n)'''
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]  # 分片法[:]建立一个列表的副本
        while (i > 0):
            self.percDown(i)
           i = i - 1
    def percUp(self,i):
        '''如果新添加的项小于其父项，则我们可以将项与其父项交换。'''
        while i // 2 > 0:    # // 取整除 - 返回商的整数部分（向下取整）
            if self.heapList[i] < self.heapList[i//2]:
               tmp = self.heapList[i // 2]
               self.heapList[i // 2] = self.heapList[i]
               self.heapList[i] = tmp
            i = i // 2
    def percDown(self, i):
        &#39;&#39;&#39;将新的根节点沿着一条路径“下沉”，直到比两个子节点都小。&#39;&#39;&#39;
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            i = mc
    def minChild(self, i):
        &#39;&#39;&#39;在选择下沉路径时，如果新根节点比子节点大，那么选择较小的子节点与之交换。&#39;&#39;&#39;
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1
    def delMin(self):
        &#39;&#39;&#39;移走根节点的元素（最小项）后如何保持堆结构和堆次序&#39;&#39;&#39;
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval
bh = BinHeap()
bh.buildHeap([9,5,6,2,3])
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())

La dernière partie concernant le tas binaire consiste à trouver un moyen de générer un "tas" à partir d'une liste non ordonnée. La première chose à laquelle nous pensons est d’insérer tour à tour chaque élément de la liste non ordonnée dans le tas. Pour une liste triée, nous pouvons utiliser la recherche binaire pour trouver la position appropriée, puis insérer la valeur clé dans le tas à la position suivante, avec une complexité temporelle de O(logn). De plus, l'insertion d'un élément dans la liste nécessite de déplacer certains autres éléments de la liste pour faire de la place au nouveau nœud, et la complexité temporelle est O(n). Par conséquent, le coût total de l’utilisation de la méthode insert est O(nlogn). En fait, nous pouvons générer directement la liste entière dans un tas et contrôler la surcharge totale sur O(n). Le listing 6 montre l'opération de génération d'un tas.

Il semble un peu incroyable qu'un tas binaire puisse être généré avec une surcharge O(n), donc je ne le prouverai pas ici. Mais la clé pour comprendre qu'un tas peut être généré avec une surcharge O(n) réside dans le fait que le facteur de connexion est basé sur la hauteur de l'arbre. Pour de nombreuses opérations dans buildHeap, la hauteur de l'arborescence est inférieure à logn.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!