—–在堆中插入元素,并调整堆.因为插入后可能破坏堆的性质.
删除元素. —–删除一个元素,并调整堆,删除元素也可能破坏堆的性质.
获取对顶元素. —–获取而不删除....本文选用第二种方案.先形成完全二叉树,然后从最后一个非叶子节点开始,遍历所有的”有孩子节点的节点”,进行调整,直至调整到根节点.这是一种从下而上的调整策略.
如下图所示:
?...注意,图中在每个父节点,只调整了一次,这是选取的数据巧合.真正的调整方法为:将当前节点与其左右节点相比,取其中较大的值交换,然后递归的对与其交换的节点进行调整,直到没有交换或者到达叶子节点....此时考虑的是,将当前调整的元素,下沉到合适的位置
插入元素
插入元素,直接在数据的最后一位添加一个元素,就相当于放在了堆的最后一位,然后调整此节点.调整方式为:将插入节点和父节点进行比较,如果大于父节点...,则交换值,并且对其父节点进行上浮.