最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

数据结构与算法-08堆 全球最新

来源:博客园

堆(Heap)是一种特殊的树形数据结构,它满足以下两个条件:


【资料图】

堆是一棵完全二叉树,即除了最后一层,其他层都是满的,最后一层从左到右填满。

堆中每个节点的值都大于等于(或小于等于)其子节点的值,这种性质称为堆序性。

根据堆序性,堆可以分为两种类型:

  • 大根堆(Max Heap):每个节点的值都大于等于其子节点的值。
  • 小根堆(Min Heap):每个节点的值都小于等于其子节点的值。

堆的主要应用是在排序算法中,例如堆排序(Heap Sort)优先队列(Priority Queue)。堆排序是一种基于堆的排序算法,它的时间复杂度为O(nlogn),空间复杂度为O(1)。优先队列是一种数据结构,它可以用堆来实现,用于维护一组元素中的最大值或最小值。

堆可以使用数组来实现,具体实现方式为:

对于一个节点i,它的左子节点为2i+1,右子节点为2i+2。

对于一个节点i,它的父节点为(i-1)/2。

以下是一个简单的Python示例代码,演示了如何使用数组实现大根堆:

class MaxHeap:    def __init__(self):        self.heap = []    def push(self, value):        self.heap.append(value)        self._sift_up(len(self.heap) - 1)    def pop(self):        if len(self.heap) == 0:            raise ValueError("Heap is empty")        value = self.heap[0]        last_value = self.heap.pop()        if len(self.heap) > 0:            self.heap[0] = last_value            self._sift_down(0)        return value    def _sift_up(self, index):        parent_index = (index - 1) // 2        while index > 0 and self.heap[index] > self.heap[parent_index]:            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]            index = parent_index            parent_index = (index - 1) // 2    def _sift_down(self, index):        left_child_index = 2 * index + 1        right_child_index = 2 * index + 2        largest_index = index        if left_child_index < len(self.heap) and self.heap[left_child_index] > self.heap[largest_index]:            largest_index = left_child_index        if right_child_index < len(self.heap) and self.heap[right_child_index

Python中的heapq模块

Python中的heapq模块提供了一些堆操作的函数,包括将列表转换为堆、将元素添加到堆、从堆中删除元素、获取堆中的最小值或最大值等。heapq模块使用的是小根堆,即堆中的最小值在堆顶。

常用的heapq函数:

  • heapify(iterable):将可迭代对象转换为堆。
  • heappush(heap, item):将元素添加到堆中。
  • heappop(heap):从堆中删除并返回最小值。
  • heappushpop(heap, item):将元素添加到堆中,并返回堆中的最小值。
  • heapreplace(heap, item):从堆中删除并返回最小值,并将元素添加到堆中。
  • nlargest(n, iterable[, key]):返回可迭代对象中最大的n个元素。
  • nsmallest(n, iterable[, key]):返回可迭代对象中最小的n个元素。

使用示例:

import heapq# 将列表转换为堆heap = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3# 将列表转换为堆heap = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]heapq.heapify(heap)print(heap)# 将元素添加到堆中heapq.heappush(heap, 0)print(heap)# 从堆中删除并返回最小值min_value = heapq.heappop(heap)print(min_value)print(heap)# 将元素添加到堆中,并返回堆中的最小值min_value = heapq.heappushpop(heap, 7)print(min_value)print(heap)# 从堆中删除并返回最小值,并将元素添加到堆中min_value = heapq.heapreplace(heap, 8)print(min_value)print(heap)# 返回可迭代对象中最大的n个元素largest = heapq.nlargest(3, heap)print(largest)# 返回可迭代对象中最小的n个元素smallest = heapq.nsmallest(3, heap)print(smallest)

在这个示例代码中,首先定义了一个列表heap,然后使用heapq.heapify函数将其转换为堆。接着使用heapq.heappush函数将元素0添加到堆中,使用heapq.heappop函数从堆中删除并返回最小值,使用heapq.heappushpop函数将元素7添加到堆中,并返回堆中的最小值,使用heapq.heapreplace函数从堆中删除并返回最小值,并将元素8添加到堆中。最后使用heapq.nlargest函数返回堆中最大的3个元素,使用heapq.nsmallest函数返回堆中最小的3个元素。

关键词: