Java语言实现最大堆代码示例

Java语言实现最大堆代码示例

最大堆

最大堆的特点是父元素比子元素大，并且是一棵完全二叉树。

data[1]开始存，data[0]空着不用。也可以把data[0]当成size来用。

public class MaxHeap> {

private T[] data;

private int size;

private int capacity;

public MaxHeap(int capacity) {

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

size = 0;

this.capacity = capacity;

}

public int size() {

return this.size;

}

public Boolean isEmpty() {

return size == 0;

}

public int getCapacity() {

return this.capacity;

}

/**

* @return 查看最大根(只看不删, 与popMax对比)

*/

public T seekMax() {

return data[1];

}

public void swap(int i, int j) {

if (i != j) {

T temp = data[i];

data[i] = data[j];

data[j] = temp;

}

}

public void insert(T item) {

size++;

data[size] = item;

shiftUp(size);

}

/**

* @return 弹出最大根(弹出意味着删除, 与seekMax对比)

*/

public T popMax() {

swap(1, size--);

shiftDown(1);

return data[size + 1];

}

/**

* @param child 孩子节点下角标是child，父节点下角表是child/2

*/

public void shiftUp(int child) {

while (child > 1ketGOPDsf && data[child].compareTo(data[child / 2]) > 0) {

swap(child, child / 2);

child = child / 2;

}

}

/**

* @param a data数组中某个元素的下角标

* @param b data数组中某个元素的下角标

* @return 哪个元素大就返回哪个的下角标

*/

private int max(int a, int b) {

if (data[a].compareTo(data[b]) < 0) {

//如果data[b]大

return b;

//返回b

} else {

//如果data[a]大

return a;

//返回a

}

}

/**

* @param a data数组中某个元素的下角标

* @param b data数组中某个元素的下角标

* @param c data数组中某个元素的下角标

* @return 哪个元素大就返回哪个的下角标

*/

private int max(int a, int b, int c) {

int biggest = max(a, b);

biggest = max(biggest, c);

return biggest;

}

/**

* @param father 父节点下角标是father,左右两个孩子节点的下角表分别是：father*2 和 father*2+1

*/

public void shiftDown(int father) {

while (true) {

int lchild = father * 2;

//左孩子

int rchild = father * 2 + 1;

//右孩子

int newFather = father;

//newFather即将更新，父、左、右三个结点谁大，newFather就是谁的下角标

if (lchild > size) {

//如果该father结点既没有左孩子，也没有右孩子

return;

} else if (rchild > size) {

//如果该father结点只有左孩子，没有右孩子

newFather = max(father, lchild);

} else {

//如果该father结点既有左孩子，又有右孩子

newFather = max(father, lchild, rchild);

}

if (newFather == father) {

//说明father比两个子结点都要大，表名已经是大根堆，不用继续调整了

return;

} else {

//否则，还需要继续调整堆，直到满足大根堆条件为止

swap(father, newFather);

//值进行交换

father = newFather;

//更新father的值，相当于继续调整shiftDown(newFather)

}

}

}

public static void main(String[] args) {

//创建大根堆

MaxHeap maxHeap = new MaxHeap(100);

//向堆里存

for (int i = 0; i < 100; i++) {

maxHeap.insert((int) (Math.random() * 100));

}

//创建数组

Integer[] arr = new Integer[100];

//从堆里取，放进数组里

for (int i = 0; i < 100; i++) {

arr[i] = maxHeap.popMax();

System.out.print(arr[i] + " ");

}

System.out.println();

}

}

最大堆：shiftDown()函数与上面不一样

public class MaxHeap> {

private T[] data;

private int size;

private int capacihttp://ty;

public MaxHeap(int capacity) {

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

this.capacity = capacity;

size = 0;

}

public int size() {

return size;

}

public Boolean isEmpty() {

return size == 0;

}

public void insert(T item) {

data[size + 1] = item;

size++;

shiftUp(size);

}

/**

* @return 弹出最大根(弹出意味着删除, 与seekMax对比)

*/

public T popMax() {

T ret = data[1];

swap(1, size);

size--;

shiftDown(1);

return ret;

}

/**

* @return 查看最大根(只看不删, 与popMax对比)

*/

public T seekMax() {

return data[1];

}

public void swap(int i, int j) {

if (i != j) {

T temp = data[i];

data[i] = data[j];

data[j] = temp;

}

}

public void shiftUp(int k) {

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

swap(k, k / 2);

k /= 2;

}

}

public void shiftDown(int father) {

while (2 * father <= size) {

int newFather = 2 * father;

if (newFather + 1 <= size && data[newFather + 1].compareTo(data[newFather]) > 0) {

//data[j] data[j+1]两者取大的那个

newFather = newFather + 1;

}

if (data[father].compareTo(data[newFather]) >= 0) {

break;

} else {

swap(father, newFather);

//值进行交换

father = newFather;

//newFather是(2*father)或者是(2*father+1),也就是继续shiftDown(newFather);

}

}

}

public static void main(String[] args) {

//创建大根堆

MaxHeap maxHeap = new MaxHeap(100);

//向堆里存

for (int i = 0; i < 100; i++) {

maxHeap.insert((int) (Math.random() * 100));

}

//创建数组

Integer[] arr = new Integer[100];

//从堆里取，放进数组里

for (int i = 0; i < 100; i++) {

arr[i] = maxHeap.popMax();

System.out.print(arr[i] + " ");

}

System.out.println();

}

}

总结

以上就是本文关于java语言实现最大堆代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。