可以使用数组来模拟堆,并且需要实现三个基本操作:插入元素、获取堆顶元素、删除堆顶元素。 1. 插入元素(push 操作) 将新元素插入数组的末尾。 然后将这个新元素向上调整,直到其满足堆的性质(即父节点的值大于等于当前节点的值)。 向上调整过程(上浮): 比较当前元素与其父节点的大小。如果当前元素大于其父节点,交换两者的位置。 重复此过程,直到当前元素不再大于其父节点,或者当前元素已经成为根节点。 2. 获取堆顶元素(top 操作) 直接返回数组的第一个元素(即根节点)。 如果堆为空,返回 "empty"。 3. 删除堆顶元素(pop 操作) 用数组的最后一个元素替换堆顶元素,然后移除最后一个元素。 将新的堆顶元素向下调整,直到其满足堆的性质(即当前节点的值大于等于其子节点的值)。 向下调整过程(下沉): 比较当前节点与其两个子节点的大小。 如果当前节点小于最大的子节点,交换它们的位置。 重复此过程,直到当前节点不再小于它的子节点,或者当前节点没有子节点。
点赞

相关推荐

点赞 评论 收藏
分享
吴offer选手:我卡在笔试才是最好笑的,甚至没给我发过笔试链接
投递哔哩哔哩等公司7个岗位
点赞 评论 收藏
分享
牛客网
牛客企业服务