如何插入到实施为二叉树的二进制最大堆？ [英] How to insert into a binary max heap implemented as a binary tree?

问题描述

在实现为二叉树（其中每个节点存储一个指向它的父，左子和右子）的二进制最大堆，如果你有指向堆的根，你将如何实现一个插件操作？什么应该发生的是第一被插入在最后一行的最后一个元素节点。对于基于阵列的，你可以追加到数组，但树的基础的实施，你将如何找到正确的位置？

In a binary max heap implemented as a binary tree (where each node stores a pointer to its parent, left child, and right child), if you have the pointer to the root of the heap, how would you implement an insert operation? What's supposed to happen is the node first gets inserted as the last element in the last row. For array based, you could append to the array, but for tree based implementation, how would you find the right spot?

推荐答案

如果你挂你新的顶点在你的树的任何叶子（左或右的继任者，无所谓），然后从这个新修的堆顶点顶端（即，关于每个其他顶点与继任者，将其交换的更大后继，如果需要爬上），您的新元素将发现它不破坏堆应有的位置。然而，这只会向你保证，所有其他的插入操作将需要O（高）时，其中h是树的最大高度。 这是更好地重新present堆作为一个数组，很明显，因为这样它保证每个插入操作需要O（logN）的时间。

If you hang you new vertex under any leaf of your tree (as left or right successor, doesn't matter), and then repair the heap from this new vertex to the top (that is, regarding every other vertex with successors, swap it with the greater successor and climb up if needed), your new element will find it's rightful place without breaking the heap. However, this will only guarantee you that every other insert operation will take O(h) time, where h is the maximum height of the tree. It's better to represent heap as an array, obviously, because that way it's guaranteed that every insert operation will take O(logN) time.

这篇关于如何插入到实施为二叉树的二进制最大堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！