RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 731067
Accepted
faoxis
faoxis
Asked:2020-10-15 19:00:00 +0000 UTC2020-10-15 19:00:00 +0000 UTC 2020-10-15 19:00:00 +0000 UTC

二进制堆实现

  • 772

我做了这个二进制堆实现:

public class BinaryHeap {

    private int[] elements;

    public BinaryHeap(int[] elements) {
        this.elements = elements;
        for (int i = elements.length / 2 - 1; i >= 0; --i) {
            siftDown(i);
        }
    }

    public void add(int element) {
        int[] newElements = new int[elements.length + 1];
        System.arraycopy(elements, 0, newElements, 0, elements.length);
        newElements[newElements.length - 1] = element;
        elements = newElements;

        siftUp(elements.length - 1);
    }

    public int extractMax() {
        assert !isEmpty();

        int result = elements[0];
        elements[0] = elements[elements.length - 1];
        deleteLast();

        if (!isEmpty()) {
            siftDown(0);
        }

        return result;
    }

    public boolean isEmpty() {
        return elements.length == 0;
    }

    private void deleteLast() {
        if (elements.length > 1) {
            int[] newElements = new int[elements.length - 1];
            System.arraycopy(elements, 0, newElements, 0, elements.length - 1);
            elements = newElements;
        } else {
            elements = new int[0];
        }
    }

    private void siftDown(int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        int largest = i;
        if (left < elements.length && elements[left] > elements[i]) {
            largest = left;
        }
        if (right < elements.length && elements[right] > elements[i]) {
            largest = right;
        }
        if (largest != i) {
            swap(i, largest);
            siftDown(largest);
        }

    }

    /**
     * Проталкивание элемента наверх
     * @param i - индес массива
     */
    private void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (elements[i] < elements[parent])
                return;
            swap(i, parent);
            i = parent;
        }
    }




    private void swap(int index1, int index2) {
        int temp = elements[index1];
        elements[index1] = elements[index2];
        elements[index2] = temp;
    }

    public int[] getElements() {
        int[] elementsCopy = new int[elements.length];
        System.arraycopy(elements, 0, elementsCopy, 0, elements.length);
        return elementsCopy;
    }

}

我写了这个小测试来测试它:

    @Test
    public void all() throws Exception {
        BinaryHeap heap = new BinaryHeap(new int[] {});
        heap = new BinaryHeap(new int[]{2, 42, 525, 35, 63, 81});

        for (int i : heap.getElements()) {
            System.out.print(i + " ");
        }
        System.out.println();

        heap.getElements()[0] = 1241251;
        assertEquals(heap.getElements()[0], 525);

        heap.add(2425);
        heap.add(1);

        List<Integer> numbers = new ArrayList<>();
        while (!heap.isEmpty()) {
            numbers.add(heap.extractMax());
        }
//        numbers.forEach(e -> System.out.print(e + " "));

        assertEquals((int) numbers.get(0), 2425);
        assertEquals((int) numbers.get(1), 525);
        assertEquals((int) numbers.get(2), 81);
        assertEquals((int) numbers.get(3), 63);
        assertEquals((int) numbers.get(4), 42);
        assertEquals((int) numbers.get(5), 35);
        assertEquals((int) numbers.get(6), 2);
        assertEquals((int) numbers.get(7), 1);
    }

问题出在方法extractMax上。并不总是采用最大数量。怎么做才对?

java
  • 1 1 个回答
  • 10 Views

1 个回答

  • Voted
  1. Best Answer
    angry
    2020-10-16T05:45:50Z2020-10-16T05:45:50Z

    方法错误shiftDown。在第二个条件下,您需要比较 with elements[largest]和 not elements[i],如下所示:

    private void siftDown(int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
    
        int largest = i;
        if (left < elements.length && elements[left] > elements[i]) {
            largest = left;
        }
        if (right < elements.length && elements[right] > elements[largest]) { 
            largest = right;
        }
        if (largest != i) {
            swap(i, largest);
            siftDown(largest);
        }
    }
    

    当顶点的值小于两个孩子,而左孩子大于右孩子时,在所有情况下都会重现错误。

    • 3

相关问题

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    Python 3.6 - 安装 MySQL (Windows)

    • 1 个回答
  • Marko Smith

    C++ 编写程序“计算单个岛屿”。填充一个二维数组 12x12 0 和 1

    • 2 个回答
  • Marko Smith

    返回指针的函数

    • 1 个回答
  • Marko Smith

    我使用 django 管理面板添加图像,但它没有显示

    • 1 个回答
  • Marko Smith

    这些条目是什么意思,它们的完整等效项是什么样的

    • 2 个回答
  • Marko Smith

    浏览器仍然缓存文件数据

    • 1 个回答
  • Marko Smith

    在 Excel VBA 中激活工作表的问题

    • 3 个回答
  • Marko Smith

    为什么内置类型中包含复数而小数不包含?

    • 2 个回答
  • Marko Smith

    获得唯一途径

    • 3 个回答
  • Marko Smith

    告诉我一个像幻灯片一样创建滚动的库

    • 1 个回答
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Алексей Шиманский 如何以及通过什么方式来查找 Javascript 代码中的错误? 2020-08-03 00:21:37 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    user207618 Codegolf——组合选择算法的实现 2020-10-23 18:46:29 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5