现在的位置: 首页 > 面试题 > 正文

堆的 shift up

2022年01月10日 面试题 ⁄ 共 1250字 ⁄ 字号 暂无评论
博客主机

本小节介绍如何向一个最大堆中添加元素,称为 shift up。

 

假设我们对下面的最大堆新加入一个元素52,放在数组的最后一位,52大于父节点16,此时不满足堆的定义,需要进行调整。

 

 

 

首先交换索引为 5 和 11 数组中数值的位置,也就是 52 和 16 交换位置。

 

 

 

此时 52 依然比父节点索引为 2 的数值 41 大,我们还需要进一步挪位置。

 

 

 

这时比较 52 和 62 的大小,52 已经比父节点小了,不需要再上升了,满足最大堆的定义。我们称这个过程为最大堆的 shift up。

 

Java 实例代码

源码包下载:Download

 

src/runoob/heap/HeapShiftUp.java 文件代码:

package runoob.heap;

 

/**

* 往堆中添加一元素

*/

public class HeapShiftUp<T extends Comparable> {

 

protected T[] data;

protected int count;

protected int capacity;

 

// 构造函数, 构造一个空堆, 可容纳capacity个元素

public HeapShiftUp(int capacity){

data = (T[])new Comparable[capacity+1];

count = 0;

this.capacity = capacity;

}

// 返回堆中的元素个数

public int size(){

return count;

}

 

// 返回一个布尔值, 表示堆中是否为空

public boolean isEmpty(){

return count == 0;

}

// 像最大堆中插入一个新的元素 item

public void insert(T item){

assert count + 1 <= capacity;

data[count+1] = item;

count ++;

shiftUp(count);

}

// 交换堆中索引为i和j的两个元素

private void swap(int i, int j){

T t = data[i];

data[i] = data[j];

data[j] = t;

}

 

//********************

//* 最大堆核心辅助函数

//********************

private void shiftUp(int k){

 

while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){

swap(k, k/2);

k /= 2;

}

}

 

// 测试 HeapShiftUp

public static void main(String[] args) {

HeapShiftUp<Integer> heapShiftUp = new HeapShiftUp<Integer>(100);

int N = 50; // 堆中元素个数

int M = 100; // 堆中元素取值范围[0, M)

for( int i = 0 ; i < N ; i ++ )

heapShiftUp.insert( new Integer((int)(Math.random() * M)) );

System.out.println(heapShiftUp.size());

 

}

}

Wopus问答

【上篇】
【下篇】

Wopus问答

给我留言

留言无头像?


×