`

二叉堆的数组实现

阅读更多
package com.hengyunsoft.test;

import java.util.Comparator;
import java.util.Random;

import edu.emory.mathcs.backport.java.util.Arrays;

public class PriorityArray<E> {

/**
* 当前已用大小
*/
private int size;

private Object[] e;

private Comparator<E> comparator;

public PriorityArray(int capacity, Comparator<E> comparator) {

e = new Object[capacity];
this.comparator = comparator;
size = 0;
}

/**
*
* @param obj
*            not null
*/
public void put(E obj) {

if (obj == null)
return;
e[size] = obj;
swapFZ(size);
++size;
}

private void swapFZ(int children) {
if (children <= 0) {
return;
}

// 找父节点
// 左:left = 2p+1
// 右:left = 2p+2
int p;
if ((children & 1) == 1) {
// 奇数
p = (children - 1) >>> 1;
} else {
// 偶数
p = (children - 2) >>> 1;
}

System.out.print("孩子:" + children + " value :" +(E) e[children]);
System.out.print("    父亲:" + p + " value :" +(E) e[p]);
if (comparator.compare((E) e[children], (E) e[p]) < 0) {
swap(children, p);
System.out.println("进行交互");
swapFZ(p);
} else {
System.out.println("不会进行交互");
}
}

private void swap(int x, int y) {
final Object temp = e[x];
e[x] = e[y];
e[y] = temp;
}

public static void main(String[] args) {

System.out.print(1 << 1 + 1);

PriorityArray<Integer> arr = new PriorityArray<>(100,
new Comparator<Integer>() {

@Override
public int compare(Integer x, Integer y) {
return Integer.compare(x, y);
}
});

Random random = new Random();

for (int i = 0; i < arr.e.length; i++) {
arr.put(random.nextInt(10000));
}



for (int j = 0,nextFlag=1,i=0; j < arr.size; j++) {
if(j < nextFlag){
System.out.print(arr.e[j] + "   ");

}else {

System.out.println();
System.out.print(arr.e[j] + "   ");

nextFlag += 2 << i;
i++;
}
}
System.out.println();
System.out.println(Arrays.toString(arr.e));
for (int i = 0; i < arr.e.length; i++) {
System.out.print(arr.pop() + "   ");
}
}

public E pop() {

if (size == 0)
return null;
E result = (E) e[0];

e[0] = e[size - 1];
swapZF(0);
--size;
return result;
}

private void swapZF(int p) {

final int left = (p << 1) + 1;
final int right = left + 1;
if (left >= size) {
return;
}
if (right >= size) {
if (comparator.compare((E) e[left], (E) e[p]) < 0) {
swap(left, p);
swapZF(left);
}
return;
}

int minIndex = right;
if (comparator.compare((E) e[left], (E) e[right]) < 0) {
minIndex = left;
}

if (comparator.compare((E) e[minIndex], (E) e[p]) < 0) {
swap(minIndex, p);
swapZF(minIndex);
}
}
}
分享到:
评论

相关推荐

    二叉堆代码

    二叉堆的实现通常采用数组的方式,因为完全二叉树的特性可以方便地映射到一维数组上。例如,如果根节点在数组中的位置为1,那么它的左子节点就在位置2,右子节点在位置3(假设数组下标从1开始)。这种映射规则使得堆...

    php 的二叉堆操作

    总结来说,PHP的二叉堆操作涉及到对数据结构的理解和实现,包括插入、删除等基本操作,以及如何通过数组来表示和调整二叉堆。掌握这些概念和技巧,对于提升PHP程序员的技能水平和解决复杂问题的能力大有裨益。

    C# 二叉堆

    数组实现简单且空间效率高,但操作起来不如自定义类灵活。自定义类可以更好地封装堆的特性,包括插入、删除、调整等操作。一般情况下,堆的根节点存储在数组的索引0处,其左子节点在索引2i+1,右子节点在索引2i+2...

    dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告

    dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告

    二叉堆(最小堆)+二项堆+斐波那契堆

    二叉堆、二项堆和斐波那契堆是数据结构中的重要概念,它们都是堆数据结构的不同变体,主要用于高效地实现某些特定操作,如查找最大或最小元素、优先队列以及各种排序算法。在C++编程语言中,理解和实现这些堆结构...

    C++二叉堆实现.zip

    在C++中,我们可以自定义二叉堆的数据结构并实现相关操作,如插入元素、删除最小/最大元素、调整堆等。 在给定的压缩包文件"C++二叉堆实现.zip"中,包含了两个文件:MyBinaryHeapTest.cpp 和 MyBinaryHeap.h。这...

    二叉堆、并查集和树状数组.pdf

    - **存储方式**:采用数组实现,根节点位于数组的第1个位置,对于任意节点`K`,其左孩子位于`2K`位置,右孩子位于`2K + 1`位置,父节点位于`[K / 2]`位置。 ##### 4. 堆的操作细节 - **删除最小值元素**:通过...

    易语言二叉堆

    在易语言中实现二叉堆,可以帮助我们高效地执行一些操作,如查找最大或最小元素、插入元素以及删除元素等。 首先,我们要理解二叉堆的两种基本类型:最大堆和最小堆。最大堆中,每个父节点的值都大于或等于其子节点...

    二叉堆的相关代码.zip二叉堆的学习与思考

    在二叉堆的实现中,通常使用数组来存储,因为数组能够方便地支持索引访问和交换操作。对于一个完全二叉树,如果从1开始对节点进行编号,那么父节点的编号是子节点编号的一半(向下取整),而左子节点的编号是父节点...

    二叉堆:最小堆

    使用c++实现最小堆。提供常见操作,如堆化数组,插入,删除,堆排序,遍历堆。

    易语言二叉堆源码.rar

    在二叉堆的实现中,我们通常使用数组来模拟树的结构。对于一个完全二叉树,我们可以将其从根节点开始,按从左到右、从上至下的顺序存储在数组中。数组的索引i对应的节点,其左子节点位于2i+1的位置,右子节点位于2i+...

    易语言二叉堆源码.7z

    易语言提供了丰富的内置函数,如“整数比较”、“数组操作”等,可以用来实现二叉堆的功能。 7. **源码阅读与分析**:对于压缩包中的"易语言二叉堆源码",开发者需要逐行阅读,理解每段代码的作用,包括数据结构的...

    二叉堆:最大堆

    使用c++实现最大堆。提供常见操作,如插入、删除、堆化数组、堆排序、上下调整、向下调整。

    易语言源码易语言二叉堆源码.rar

    本压缩包“易语言源码易语言二叉堆源码.rar”提供了易语言实现的二叉堆数据结构的源代码,对于学习易语言以及理解二叉堆这一数据结构的实现非常有帮助。 二叉堆是计算机科学中一种重要的数据结构,通常分为最大堆和...

    二叉堆的C语言实现知识

    - 在数组实现中,通常数组的大小会比实际元素数量多一个,以避免在边界处理时的复杂性。 这个C语言实现的二叉堆虽然简单,但足以处理基本的堆操作。通过实践这些操作,不仅可以加深对二叉堆的理解,也有助于提高...

    12B1 完全二叉堆:结构1

    总结来说,完全二叉堆是基于数组的高效数据结构,常用于实现优先队列,它利用二叉树的逻辑结构和数组的物理存储,提供快速的插入、删除和查询操作。在实际编程中,通过维护堆序性,可以确保最大值总是在根节点,从而...

    使用数组实现二叉树

    7. **应用**:数组实现二叉树常用于解决特定问题,如堆排序(二叉堆)、哈夫曼编码(哈夫曼树)等。这些场景下,数组的特性使得操作更高效。 总的来说,虽然数组实现二叉树在某些方面不如链式结构灵活,但它在特定...

    Python实现的简单二叉堆(最小堆)示例

    在Python中实现二叉堆,我们通常会利用数组来模拟堆结构,因为数组天然支持索引访问和交换操作。这里,我们将探讨如何构建和操作一个简单的最小堆。 首先,我们需要理解二叉堆的几个基本操作: 1. **插入元素...

    java编程实现优先队列的二叉堆代码分享

    3. Java 实现二叉堆的优先队列:使用 Java 语言实现二叉堆的优先队列,可以使用数组来存储元素,并使用 swim 和 sink 方法来维护堆的有序性。 4. swim 方法的实现:swim 方法用于将元素上浮到正确的位置,以维护堆...

Global site tag (gtag.js) - Google Analytics