Maison >développement back-end >Tutoriel Python >Quels sont les scénarios d'utilisation du tas et de la file d'attente prioritaire en Python ?
Quels sont les scénarios d'utilisation du tas et de la file d'attente prioritaire en Python ?
Heap est une structure arborescente binaire spéciale qui est souvent utilisée pour maintenir efficacement une collection dynamique. Le module heapq en Python fournit une implémentation de tas et peut facilement effectuer des opérations sur le tas.
La file d'attente prioritaire est également une structure de données spéciale différente de la file d'attente ordinaire, chaque élément de celle-ci est associé à une priorité. L'élément ayant la priorité la plus élevée est supprimé en premier. Le module heapq en Python peut également implémenter la fonction de file d'attente prioritaire.
Ci-dessous, nous présentons quelques scénarios spécifiques d'utilisation du tas et de la file d'attente prioritaire, et donnons des exemples de code pertinents.
import heapq def top_k_smallest(nums, k): heap = [] for num in nums: heapq.heappush(heap, num) if len(heap) > k: heapq.heappop(heap) return heap nums = [5, 3, 8, 2, 7, 1, 9] k = 3 result = top_k_smallest(nums, k) print(result) # 输出 [3, 2, 1]
import heapq def merge_sorted_arrays(arrays): result = [] pq = [] for array in arrays: if array: heapq.heappush(pq, (array[0], array)) while pq: smallest, array = heapq.heappop(pq) result.append(smallest) if array[1:]: heapq.heappush(pq, (array[1], array[1:])) return result arrays = [[1, 3, 5], [2, 4, 6], [0, 7, 8]] result = merge_sorted_arrays(arrays) print(result) # 输出 [0, 1, 2, 3, 4, 5, 6, 7, 8]
import heapq def median(nums): min_heap = [] max_heap = [] for num in nums: if len(max_heap) == 0 or num <= -max_heap[0]: heapq.heappush(max_heap, -num) else: heapq.heappush(min_heap, num) if len(max_heap) > len(min_heap) + 1: heapq.heappush(min_heap, -heapq.heappop(max_heap)) elif len(min_heap) > len(max_heap): heapq.heappush(max_heap, -heapq.heappop(min_heap)) if len(max_heap) > len(min_heap): return -max_heap[0] elif len(min_heap) > len(max_heap): return min_heap[0] else: return (-max_heap[0] + min_heap[0]) / 2 nums = [4, 2, 5, 7, 1, 8, 3, 6] result = median(nums) print(result) # 输出 4.5
Ci-dessus sont quelques scénarios d'utilisation courants et des exemples de codes de tas et de file d'attente prioritaire en Python. Les tas et les files d'attente prioritaires sont des structures de données couramment utilisées, et maîtriser leur utilisation est très utile pour résoudre certains problèmes complexes.
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!