简体中文（ZH-CN）English（EN）繁体中文（ZH-TW）日本語（JA）한국어（KO）Melayu（MS）Français（FR）Deutsch（DE）
Rumah
Artikel
Soal Jawab
Kursus
Topik
Muat turun
Permainan
Kamus
kemas kini terkini

Rumah  >  Artikel  >  Java  >  Penjelasan terperinci tentang prinsip dan pelaksanaan timbunan minimum dan timbunan maksimum struktur data Java

Penjelasan terperinci tentang prinsip dan pelaksanaan timbunan minimum dan timbunan maksimum struktur data Java

WBOY
WBOYke hadapan
2022-09-05 17:30:292426semak imbas

Artikel ini membawakan anda pengetahuan yang berkaitan tentang java Dalam sains komputer, pelaksanaan heap ialah struktur data khas berdasarkan pepohon, yang boleh digunakan pada tatasusunan dan memuaskan sifat timbunan, mari kita bercakap tentang timbunan dalam struktur data Java Mereka yang berminat boleh mengetahui lebih lanjut.

Penjelasan terperinci tentang prinsip dan pelaksanaan timbunan minimum dan timbunan maksimum struktur data Java

Kajian yang disyorkan: "tutorial video java"

1 >

Struktur data timbunan mempunyai banyak bentuk, termasuk; timbunan 2-3, timbunan B, timbunan Fibonacci, dan yang paling biasa digunakan dalam API Java ialah timbunan binari yang digunakan untuk melaksanakan baris gilir keutamaan, yang Diperkenalkan oleh JWJ Williams pada tahun 1964 sebagai struktur data untuk algoritma heapsort. Selain itu, timbunan juga sangat penting dalam beberapa algoritma graf yang cekap seperti algoritma Dijkstra.

2. Struktur data heap

Dalam sains komputer, pelaksanaan heap ialah struktur data khas berdasarkan pepohon, yang boleh membina struktur pepohon pada badan tatasusunan, dan memenuhi sifat-sifat timbunan;

Timbunan minimum: Jika P ialah nod induk C, maka kunci (atau nilai) P hendaklah kurang daripada atau sama dengan nilai C yang sepadan.

Timbunan maks: Bertentangan dengan takrif timbunan min, timbunan maks (timbunan maks), kunci (atau nilai) P adalah lebih besar daripada nilai yang sepadan bagi C.

3. Pelaksanaan kod timbunan

1 Pengenalan pelaksanaan

Pelaksanaan timbunan dalam Java API terutamanya ditunjukkan dalam delay queue Untuk melaksanakan timbunan binari, Brother Fu di sini mengasingkan bahagian kod ini untuk mengetahui tentang pelaksanaan longgokan kecil dan longgokan besar.

Daripada pengenalan kepada struktur data timbunan, kita dapat melihat bahawa satu-satunya perbezaan antara timbunan kecil dan timbunan besar ialah cara mengisih unsur. Maksudnya, kaedah pengisihan adalah berbeza apabila mengisi dan mengeluarkan elemen semasa menyimpan dan mendapatkan semula elemen.

2. Pelaksanaan Heap

Apabila menyimpan elemen, heap mengikut ciri-cirinya dan akan dipindahkan ke atas melalui perbandingan elemen ekor semasa proses penyimpanan.

Pelaksanaan penambahan timbunan pada kaedah tambah akhirnya akan memanggil kaedah siftUpComparable untuk pemprosesan dalam cara pengisihan. Kaedah pengisihan compareTo ini dilaksanakan oleh MinHeap dan MaxHeap tertentu. 

private void siftUpComparable(int k, E x) {
    logger.info("【入队】元素：{} 当前队列：{}", JSON.toJSONString(x), JSON.toJSONString(queue));
    while (k > 0) {
        // 获取父节点Idx，相当于除以2
        int parent = (k - 1) >>> 1;
        logger.info("【入队】寻找当前节点的父节点位置。k：{} parent：{}", k, parent);
        Object e = queue[parent];
        // 如果当前位置元素，大于父节点元素，则退出循环
        if (compareTo(x, (E) e) >= 0) {
            logger.info("【入队】值比对，父节点：{} 目标节点：{}", JSON.toJSONString(e), JSON.toJSONString(x));
            break;
        }
        // 相反父节点位置大于当前位置元素，则进行替换
        logger.info("【入队】替换过程，父子节点位置替换，继续循环。父节点值：{} 存放到位置：{}", JSON.toJSONString(e), k);
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
    logger.info("【入队】完成 Idx：{} Val：{} \r\n当前队列：{} \r\n", k, JSON.toJSONString(x), JSON.toJSONString(queue));
}
Ambil elemen timbunan 2 sebagai contoh, seperti yang ditunjukkan dalam rajah.

Mula-mula, gantung elemen 2 ke penghujung baris gilir, kemudian hitung kedudukan nod induk melalui (k - 1) >>> bandingkan dengan elemen yang sepadan.

Proses pertukaran termasuk 2->6, 2->5, dan unsur-unsur disimpan selepas pertukaran selesai.

3. Mengalih keluar elemen

daripada timbunan sebenarnya sangat mudah, hanya padamkan elemen akar dan timbulkan terus. Tetapi langkah-langkah yang selebihnya adalah rumit, kerana selepas elemen akar dipindahkan, perlu mencari elemen minimum lain untuk berhijrah ke hujung yang bertentangan. Proses ini betul-betul bertentangan dengan memasuki timbunan Ia adalah proses migrasi ke bawah yang berterusan.

Alihkan elemen secara berterusan ke bawah. Proses ini akan membandingkan nilai nod anak kiri dan kanan dan mencari yang terkecil. Jadi keseluruhan proses akan menjadi lebih menyusahkan daripada memasuki longgokan. 

private void siftDownComparable(int k, E x) {
    // 先找出中间件节点
    int half = size >>> 1;
    while (k < half) {
        // 找到左子节点和右子节点，两个节点进行比较，找出最大的值
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        // 左子节点与右子节点比较，取最小的节点
        if (right < size && compareTo((E) c, (E) queue[right]) > 0) {
            logger.info("【出队】左右子节点比对，获取最小值。left：{} right：{}", JSON.toJSONString(c), JSON.toJSONString(queue[right]));
            c = queue[child = right];
        }
        // 目标值与c比较，当目标值小于c值，退出循环。说明此时目标值所在位置适合，迁移完成。
        if (compareTo(x, (E) c) <= 0) {
            break;
        }
        // 目标值小于c值，位置替换，继续比较
        logger.info("【出队】替换过程，节点的值比对。上节点：{} 下节点：{} 位置替换", JSON.toJSONString(queue[k]), JSON.toJSONString(c));
        queue[k] = c;
        k = child;
    }
    // 把目标值放到对应位置
    logger.info("【出队】替换结果，最终更换位置。Idx：{} Val：{}", k, JSON.toJSONString(x));
    queue[k] = x;
}

Di sini kita mengambil elemen pop timbul 1 sebagai contoh, dan kemudian menggantikan elemen di hujung timbunan ke kedudukan yang sepadan. Keseluruhan proses dibahagikan kepada 6 gambar.

Rajah 1 hingga Rajah 2, cari elemen akar dan timbul.

    Rajah 3 hingga Rajah 4, gerakkan elemen akar ke bawah, bandingkan dengan elemen anak, dan gantikan kedudukannya. Jika kedudukan ini dibandingkan dengan 8 dan kurang daripada 8, ia akan terus berhijrah ke bawah.
  • Dari Rajah 4 hingga Rajah 5, teruskan penghijrahan Kedua-dua sub-elemen yang sepadan dengan nod asal 4 kedua-duanya lebih besar daripada 8. Anda boleh berhenti pada masa ini.
  • Rajah 5 hingga Rajah 6, tukar kedudukan elemen, gantikan elemen di hujung baris gilir ke kedudukan yang sepadan dengan pengesanan migrasi ke bawah bagi elemen 1.
  • 4. Pelaksanaan longgokan kecil

Timbunan kecil ialah penjajaran jujukan positif

Ujian
public class MinHeap extends Heap<Integer> {

    @Override
    public int compareTo(Integer firstElement, Integer secondElement) {
        return firstElement.compareTo(secondElement);
    }

}

Keputusan
@Test
public void test_min_heap() {
    MinHeap heap = new MinHeap();
    // 存入元素
    heap.add(1);
    heap.add(3);
    heap.add(5);
    heap.add(11);
    heap.add(4);
    heap.add(6);
    heap.add(7);
    heap.add(12);
    heap.add(15);
    heap.add(10);
    heap.add(9);
    heap.add(8);
    // 弹出元素
    while (heap.peek() != null){
        logger.info("测试结果：{}", heap.poll());
    }
}

17:21:30.053 [utama] INFO baris gilir.PriorityQueue - [Enqueue] Elemen: 3 Baris gilir semasa: [1,null,null,null,null,null,null,null,null,null, null ]
17:21:30.055 [utama] INFO queue.PriorityQueue - [Enter the queue] Cari kedudukan nod induk nod semasa. k: 1 induk: 0
17:21:30.056 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 1 nod sasaran: 3
17:21:30.056 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Lengkap: 1 Val: 3
Baris gilir semasa: [1,3,null,null,null,null,null,null,null,null,null]

17: 21:30.056 [utama] INFO baris gilir.PriorityQueue - [Enqueue] Elemen: 5 Baris gilir semasa: [1,3,null,null,null,null,null,null,null,null,null]
17 :21: 30.056 [utama] INFO queue.PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k: 2 induk: 0
17:21:30.056 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 1 nod sasaran: 5
17:21:30.056 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Lengkap: 2 Val: 5
Baris gilir semasa: [1,3,5,null,null,null,null,null,null,null,null]

17: 21:30.056 [utama] INFO baris gilir.PriorityQueue - [Enqueue] Elemen: 11 Baris gilir semasa: [1,3,5,null,null,null,null,null,null,null,null]
17 :21: 30.056 [utama] INFO queue.PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k: 3 induk: 1
17:21:30.056 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 3 nod sasaran: 11
17:21:30.056 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Lengkap: 3 Val: 11
Baris gilir semasa: [1,3,5,11,null,null,null,null,null,null,null]

17: 21:30.056 [utama] INFO baris gilir. PriorityQueue - [Enqueue] Elemen: 4 Baris gilir semasa: [1,3,5,11,null,null,null,null,null,null,null]
17 :21: 30.056 [utama] INFO queue.PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k: 4 induk: 1
17:21:30.056 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 3 nod sasaran: 4
17:21:30.056 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Lengkap: 4 Val: 4
Baris gilir semasa: [1,3,5,11,4,null,null,null,null,null,null]

17: 21:30.056 [utama] INFO baris gilir. PriorityQueue - [Enqueue] Elemen: 6 Baris gilir semasa: [1,3,5,11,4,null,null,null,null,null,null]
17 :21: 30.056 [utama] INFO queue.PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k: 5 induk: 2
17:21:30.056 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 5 nod sasaran: 6
17:21:30.056 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Selesai: 5 Val: 6
Baris gilir semasa: [1,3,5,11,4,6,null,null,null,null,null]

17: 21:30.056 [utama] INFO baris gilir.PriorityQueue - [Enqueue] Elemen: 7 Baris gilir semasa: [1,3,5,11,4,6,null,null,null,null,null]
17 :21: 30.056 [utama] INFO queue.PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k: 6 induk: 2
17:21:30.056 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 5 nod sasaran: 7
17:21:30.056 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Selesai: 6 Val: 7
Baris gilir semasa: [1,3,5,11,4,6,7,null,null,null,null] 17:21:30.056 [ utama] gilir INFO.PriorityQueue - [Enqueue] Elemen: 12 Baris gilir semasa: [1,3,5,11,4,6,7,null,null,null,null]
17:21:30.056 [utama ] INFO baris gilir .PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k: 7 induk: 3
17:21:30.056 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 11 nod sasaran: 12
17:21:30.056 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Lengkap: 7 Val: 12
Baris gilir semasa: [1,3,5,11,4,6,7,12,null,null,null]

17: 21:30.056 [utama] INFO baris gilir. PriorityQueue - [Enqueue] Elemen: 15 Baris gilir semasa: [1,3,5,11,4,6,7,12,null,null,null]
17 :21: 30.056 [utama] INFO queue.PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k: 8 induk: 3
17:21:30.056 [utama] INFO baris gilir. PriorityQueue - [gilir] perbandingan nilai, nod induk: 11 nod sasaran: 15
17:21:30.057 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Selesai: 8 Val: 15
Baris gilir semasa: [1,3,5,11,4,6,7,12,15,null,null]

17 :21:30.057 [utama] INFO baris gilir.PriorityQueue - [Enqueue] Elemen: 10 Baris gilir semasa: [1,3,5,11,4,6,7,12,15,null,null]
17 :21 :30.057 [utama] INFO queue.PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k: 9 induk: 4
17:21:30.057 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 4 nod sasaran: 10
17:21:30.057 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Selesai: 9 Val: 10
Baris gilir semasa: [1,3,5,11,4,6,7,12,15,10,null]

17 :21:30.057 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Elemen: 9 Baris gilir semasa: [1,3,5,11,4,6,7,12,15,10,null]
17 : 21:30.057 [utama] INFO queue.PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k：10 ibu bapa：4
17:21:30.057 [utama] INFO queue.PriorityQueue - [Enter Queue] Perbandingan nilai, nod induk: 4 Target nod: 9
17:21:30.057 [utama] INFO queue.PriorityQueue - [Enter Queue] complete Idx : 10 Val: 9
Baris gilir semasa: [1,3,5,11,4,6,7,12,15,10,9]

17:21:30.057 [utama] baris gilir INFO .PriorityQueue - [Enqueue] Elemen: 8 Baris gilir semasa: [1,3,5,11,4,6,7,12,15,10,9,null,null,null,null,null,null,null ,null ,null,null,null,null,null]
17:21:30.057 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Cari kedudukan nod induk nod semasa. k: 11 induk: 5
17:21:30.057 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 6 nod sasaran: 8
17:21:30.057 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Lengkap: 11 Val: 8
Baris gilir semasa: [1,3,5,11,4,6,7,12,15,10,9,8,null,null, null, null,null,null,null,null,null,null,null,null]

17:21:30.057 [utama] INFO queue.PriorityQueue - [Dequeue] Proses penggantian, nisbah nilai nod betul. Nod atas: 1 Nod bawah: 3 Gantian kedudukan
17:21:30.057 [utama] INFO queue.PriorityQueue - [Dequeue] Bandingkan nod anak kiri dan kanan untuk mendapatkan nilai minimum. kiri: 11 kanan: 4
17:21:30.057 [utama] INFO baris gilir.PriorityQueue - [Dequeue] Proses penggantian, perbandingan nilai nod. Nod atas: 3 Nod bawah: 4 Gantian kedudukan
17:21:30.057 [utama] INFO queue.PriorityQueue - [Dequeue] Bandingkan nod anak kiri dan kanan untuk mendapatkan nilai minimum. kiri: 10 kanan: 9
17:21:30.057 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 4 Val: 8
17:21:30.057 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 1
17:21:30.057 [utama] INFO queue. PriorityQueue - [Dequeue] Proses penggantian , perbandingan nilai nod. Nod atas: 3 Nod bawah: 4 Gantian kedudukan
17:21:30.057 [utama] INFO queue.PriorityQueue - [Dequeue] Bandingkan nod anak kiri dan kanan untuk mendapatkan nilai minimum. kiri: 11 kanan: 8
17:21:30.057 [utama] INFO baris gilir.PriorityQueue - [Dequeue] Proses penggantian, perbandingan nilai nod. Nod atas: 4 Nod bawah: 8 Penggantian kedudukan
17:21:30.057 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 4 Val: 9
17:21:30.057 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 3
17:21:30.057 [utama] INFO queue. PriorityQueue - [Dequeue] Kiri dan kanan kanak-kanak Bandingkan nod untuk mendapatkan nilai minimum. kiri: 8 kanan: 5
17:21:30.057 [utama] INFO baris gilir.PriorityQueue - Proses penggantian [Dequeue], perbandingan nilai nod. Nod atas: 4 Nod bawah: 5 Penggantian kedudukan
17:21:30.057 [utama] INFO baris gilir.PriorityQueue - Proses penggantian [Dequeue], perbandingan nilai nod. Nod atas: 5 Nod bawah: 6 Penggantian kedudukan
17:21:30.057 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 5 Val: 10
17:21:30.057 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 4
17:21:30.057 [utama] INFO queue. PriorityQueue - [Dequeue] Kiri dan kanan kanak-kanak Bandingkan nod untuk mendapatkan nilai minimum. kiri: 8 kanan: 6
17:21:30.058 [utama] INFO baris gilir.PriorityQueue - [Dequeue] Proses penggantian, perbandingan nilai nod. Nod atas: 5 Nod bawah: 6 Penggantian kedudukan
17:21:30.058 [utama] INFO queue.PriorityQueue - [Dequeue] Bandingkan nod anak kiri dan kanan untuk mendapatkan nilai minimum. kiri: 10 kanan: 7
17:21:30.058 [utama] INFO baris gilir.PriorityQueue - [Dequeue] Proses penggantian, perbandingan nilai nod. Nod atas: 6 Nod bawah: 7 Penggantian kedudukan
17:21:30.058 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 6 Val: 15
17:21:30.058 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 5
17:21:30.058 [utama] INFO queue. PriorityQueue - [Dequeue] Kiri dan kanan kanak-kanak Bandingkan nod untuk mendapatkan nilai minimum. kiri: 8 kanan: 7
17:21:30.058 [utama] INFO baris gilir.PriorityQueue - Proses penggantian [Dequeue], perbandingan nilai nod. Nod atas: 6 Nod bawah: 7 Penggantian kedudukan
17:21:30.058 [utama] INFO baris gilir.PriorityQueue - Proses penggantian [Dequeue], perbandingan nilai nod. Nod atas: 7 Nod bawah: 10 Penggantian kedudukan
17:21:30.058 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 5 Val: 12
17:21:30.058 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 6
17:21:30.058 [utama] INFO queue. PriorityQueue - [Dequeue] Proses penggantian , perbandingan nilai nod. Nod atas: 7 Nod bawah: 8 Gantian kedudukan
17:21:30.058 [utama] INFO queue.PriorityQueue - [Dequeue] Bandingkan nod anak kiri dan kanan untuk mendapatkan nilai minimum. kiri: 11 kanan: 9
17:21:30.058 [utama] INFO baris gilir.PriorityQueue - [Dequeue] Proses penggantian, perbandingan nilai nod. Nod atas: 8 Nod bawah: 9 Penggantian kedudukan
17:21:30.058 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 4 Val: 15
17:21:30.058 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 7
17:21:30.058 [utama] INFO queue. PriorityQueue - [Dequeue] Proses penggantian , perbandingan nilai nod. Nod atas: 8 Nod bawah: 9 Penggantian kedudukan
17:21:30.058 [utama] INFO queue.PriorityQueue - Proses penggantian [Dequeue], perbandingan nilai nod. Nod atas: 9 Nod bawah: 11 Penggantian kedudukan
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：3 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：8
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：11 right：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：9 下节点：10 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：2 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：9
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：10 下节点：11 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：11 下节点：12 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：11
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：0 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：15

Process finished with exit code 0
小堆就是一个正序的输出结果，从小到大的排序和输出。
小堆空间：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

  • 小堆就是一个正序的输出结果，从小到大的排序和输出。
  • 小堆空间：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

5. 大堆实现

小堆是一个反序比对

public class MaxHeap extends Heap<Integer> {

    @Override
    public int compareTo(Integer firstElement, Integer secondElement) {
        return secondElement.compareTo(firstElement);
    }

}

测试

@Test
public void test_max_heap() {
    MaxHeap heap = new MaxHeap();
    // 存入元素
    heap.add(1);
    heap.add(3);
    heap.add(5);
    heap.add(11);
    heap.add(4);
    heap.add(6);
    heap.add(7);
    heap.add(12);
    heap.add(15);
    heap.add(10);
    heap.add(9);
    heap.add(8);
    // 弹出元素
    while (heap.peek() != null){
        logger.info("测试结果：{}", heap.poll());
    }
}

结果

17:23:45.079 [utama] INFO baris gilir.PriorityQueue - [Enqueue] Elemen: 3 Baris gilir semasa: [1,null,null,null,null,null,null,null,null,null, null ]
17:23:45.081 [utama] INFO queue.PriorityQueue - [Enter the queue] Cari kedudukan nod induk nod semasa. k: 1 ibu bapa: 0
17:23:45.081 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 1 Disimpan di lokasi: 1
17:23:45.081 [utama] INFO baris gilir.PriorityQueue - [Masukkan baris gilir] Idx Lengkap: 0 Val: 3
Baris gilir semasa: [3,1,null, null,null,null,null,null,null,null,null]

17:23:45.081 [utama] INFO queue.PriorityQueue - [Enqueue] Elemen: 5 Baris semasa: [3,1, null ,null,null,null,null,null,null,null,null]
17:23:45.081 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Cari kedudukan nod induk nod semasa. k: 2 ibu bapa: 0
17:23:45.081 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 3 Disimpan di lokasi: 2
17:23:45.081 [utama] baris gilir INFO.PriorityQueue - [Masukkan baris gilir] Idx Selesai: 0 Val: 5
Baris gilir semasa: [5,1,3, null,null,null,null,null,null,null,null]

17:23:45.081 [utama] INFO queue.PriorityQueue - Elemen [Enqueue]: 11 Baris semasa: [5,1, 3 ,null,null,null,null,null,null,null,null]
17:23:45.081 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Cari kedudukan nod induk nod semasa. k: 3 ibu bapa: 1
17:23:45.081 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 1 Disimpan di lokasi: 3
17:23:45.081 [utama] INFO baris gilir.PriorityQueue - [Masukkan baris gilir] Cari kedudukan nod induk nod semasa. k: 1 ibu bapa: 0
17:23:45.081 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 5 Disimpan di lokasi: 1
17:23:45.081 [utama] baris gilir INFO.PriorityQueue - [Masukkan baris gilir] Idx Selesai: 0 Val: 11
Baris gilir semasa: [11,5,3, 1,null,null,null,null,null,null,null]

17:23:45.081 [utama] INFO queue.PriorityQueue - Elemen [Enqueue]: 4 Baris semasa: [11,5, 3 ,1,null,null,null,null,null,null,null]
17:23:45.082 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Cari kedudukan nod induk nod semasa. k: 4 induk: 1
17:23:45.082 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 5 nod sasaran: 4
17:23:45.082 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Lengkap: 4 Val: 4
Baris gilir semasa: [11,5,3,1,4,null,null,null,null,null,null]

17: 23:45.082 [utama] INFO baris gilir.PriorityQueue - [Enqueue] Elemen: 6 Baris gilir semasa: [11,5,3,1,4,null,null,null,null,null,null]
17 :23: 45.082 [utama] INFO queue.PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k: 5 ibu bapa: 2
17:23:45.082 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 3 Disimpan di lokasi: 5
17:23:45.082 [utama] INFO baris gilir.PriorityQueue - [Masukkan baris gilir] Cari kedudukan nod induk nod semasa. k: 2 induk: 0
17:23:45.082 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 11 nod sasaran: 6
17:23:45.082 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Selesai: 2 Val: 6
Baris gilir semasa: [11,5,6,1,4,3,null,null,null,null,null]

17: 23:45.082 [utama] INFO baris gilir.PriorityQueue - [Enqueue] Elemen: 7 Baris gilir semasa: [11,5,6,1,4,3,null,null,null,null,null]
17 :23: 45.082 [utama] INFO queue.PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k: 6 ibu bapa: 2
17:23:45.082 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 6 Disimpan di lokasi: 6
17:23:45.082 [utama] INFO queue.PriorityQueue - [Enter the queue] Cari kedudukan nod induk nod semasa. k: 2 induk: 0
17:23:45.082 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 11 nod sasaran: 7
17:23:45.082 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Selesai: 2 Val: 7
Baris gilir semasa: [11,5,7,1,4,3,6,null,null,null,null]

17: 23:45.082 [utama] INFO baris gilir.PriorityQueue - [Enqueue] Elemen: 12 Baris gilir semasa: [11,5,7,1,4,3,6,null,null,null,null]
17 :23: 45.082 [utama] INFO queue.PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k: 7 ibu bapa: 3
17:23:45.082 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 1 Disimpan di lokasi: 7
17:23:45.082 [utama] baris gilir INFO.PriorityQueue - [Masukkan baris gilir] Cari kedudukan nod induk nod semasa. k: 3 ibu bapa: 1
17:23:45.082 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 5 Disimpan di lokasi: 3
17:23:45.082 [utama] INFO baris gilir.PriorityQueue - [Masukkan baris gilir] Cari kedudukan nod induk nod semasa. k：1 ibu bapa：0
17:23:45.082 [utama] INFO queue.PriorityQueue - [Enqueue] Proses penggantian, kedudukan nod induk dan anak diganti, dan kitaran diteruskan. Nilai nod induk: 11 Disimpan di lokasi: 1
17:23:45.082 [utama] baris gilir INFO.PriorityQueue - [Masukkan baris gilir] Idx Selesai: 0 Val: 12
Baris gilir semasa: [12,11,7, 5,4,3,6,1,null,null,null]

17:23:45.082 [utama] INFO queue.PriorityQueue - [Enqueue] Elemen: 15 Baris gilir semasa: [12,11, 7 ,5,4,3,6,1,null,null,null]
17:23:45.082 [utama] INFO queue.PriorityQueue - [Enter the queue] Cari kedudukan nod induk nod semasa. k: 8 ibu bapa: 3
17:23:45.082 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 5 Disimpan di lokasi: 8
17:23:45.082 [utama] INFO baris gilir.PriorityQueue - [Masukkan baris gilir] Cari kedudukan nod induk nod semasa. k: 3 ibu bapa: 1
17:23:45.082 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 11 Disimpan di lokasi: 3
17:23:45.082 [utama] INFO queue.PriorityQueue - [Enter the queue] Cari kedudukan nod induk nod semasa. k: 1 ibu bapa: 0
17:23:45.082 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 12 Disimpan di lokasi: 1
17:23:45.082 [utama] INFO baris gilir.PriorityQueue - [Masukkan baris gilir] Idx Selesai: 0 Val: 15
Baris gilir semasa: [15,12,7, 11,4,3,6,1,5,null,null]

17:23:45.082 [utama] INFO baris gilir.PriorityQueue - [Enqueue] Elemen: 10 Baris semasa: [15,12, 7 ,11,4,3,6,1,5,null,null]
17:23:45.082 [utama] INFO queue.PriorityQueue - [Enter the queue] Cari kedudukan nod induk nod semasa. k: 9 ibu bapa: 4
17:23:45.083 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 4 Disimpan di lokasi: 9
17:23:45.083 [utama] INFO baris gilir.PriorityQueue - [Masukkan baris gilir] Cari kedudukan nod induk nod semasa. k: 4 induk: 1
17:23:45.083 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 12 nod sasaran: 10
17:23:45.083 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Selesai: 4 Val: 10
Baris gilir semasa: [15,12,7,11,10,3,6,1,5,4,null]

17: 23:45.083 [utama] INFO baris gilir.PriorityQueue - [Masukkan baris gilir] Elemen: 9 Baris gilir semasa: [15,12,7,11,10,3,6,1,5,4,null]
17 :23 :45.083 [utama] INFO queue.PriorityQueue - [Enqueue] Cari kedudukan nod induk nod semasa. k: 10 induk: 4
17:23:45.083 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 10 nod sasaran: 9
17:23:45.083 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Selesai: 10 Val: 9
Baris gilir semasa: [15,12,7,11,10,3,6,1,5,4,9]

17: 23:45.083 [utama] INFO baris gilir. PriorityQueue - [Enqueue] Elemen: 8 Baris gilir semasa: [15,12,7,11,10,3,6,1,5,4,9,null,null, null,null ,null,null,null,null,null,null,null,null,null]
17:23:45.083 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Cari kedudukan nod induk semasa nod. k: 11 ibu bapa: 5
17:23:45.083 [utama] INFO queue.PriorityQueue - [Enqueue] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 3 Disimpan di lokasi: 11
17:23:45.083 [utama] INFO baris gilir.PriorityQueue - [Masukkan baris gilir] Cari kedudukan nod induk nod semasa. k: 5 ibu bapa: 2
17:23:45.083 [utama] INFO queue.PriorityQueue - [Masukkan baris gilir] Proses penggantian, kedudukan nod induk dan anak diganti dan kitaran diteruskan. Nilai nod induk: 7 Disimpan di lokasi: 5
17:23:45.083 [utama] INFO queue.PriorityQueue - [Enter the queue] Cari kedudukan nod induk nod semasa. k: 2 induk: 0
17:23:45.083 [utama] INFO baris gilir.PriorityQueue - [gilir] perbandingan nilai, nod induk: 15 nod sasaran: 8
17:23:45.083 [utama] INFO baris gilir. PriorityQueue - [Masukkan baris gilir] Idx Lengkap: 2 Val: 8
Baris gilir semasa: [15,12,8,11,10,7,6,1,5,4,9,3,null,null, null, null,null,null,null,null,null,null,null,null]

17:23:45.083 [utama] INFO queue.PriorityQueue - [Dequeue] Proses penggantian, nisbah nilai nod betul. Nod atas: 15 Nod bawah: 12 Penggantian kedudukan
17:23:45.083 [utama] INFO baris gilir.PriorityQueue - Proses penggantian [Dequeue], perbandingan nilai nod. Nod atas: 12 Nod bawah: 11 Penggantian kedudukan
17:23:45.083 [utama] INFO queue.PriorityQueue - [Dequeue] Bandingkan nod anak kiri dan kanan untuk mendapatkan nilai minimum. kiri: 1 kanan: 5
17:23:45.083 [utama] INFO baris gilir.PriorityQueue - [Dequeue] Proses penggantian, perbandingan nilai nod. Nod atas: 11 Nod bawah: 5 Penggantian kedudukan
17:23:45.083 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 8 Val: 3
17:23:45.083 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 15
17:23:45.083 [utama] INFO queue. PriorityQueue - [Dequeue] Proses penggantian , perbandingan nilai nod. Nod atas: 12 Nod bawah: 11 Penggantian kedudukan
17:23:45.083 [utama] INFO queue.PriorityQueue - [Dequeue] Bandingkan nod anak kiri dan kanan untuk mendapatkan nilai minimum. kiri：5 kanan：10
17:23:45.083 [utama] INFO queue.PriorityQueue - [Dequeue] Proses penggantian, perbandingan nilai nod. Nod atas: 11 Nod bawah: 10 Penggantian kedudukan
17:23:45.083 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 4 Val: 9
17:23:45.083 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 12
17:23:45.083 [utama] INFO queue. PriorityQueue - [Dequeue] Proses penggantian , perbandingan nilai nod. Nod atas: 11 Nod bawah: 10 Penggantian kedudukan
17:23:45.083 [utama] INFO queue.PriorityQueue - [Dequeue] Bandingkan nod anak kiri dan kanan untuk mendapatkan nilai minimum. kiri: 5 kanan: 9
17:23:45.083 [utama] INFO baris gilir.PriorityQueue - [Dequeue] Proses penggantian, perbandingan nilai nod. Nod atas: 10 Nod bawah: 9 Penggantian kedudukan
17:23:45.083 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 4 Val: 4
17:23:45.083 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 11
17:23:45.083 [utama] INFO queue. PriorityQueue - [Dequeue] Proses penggantian , perbandingan nilai nod. Nod atas: 10 Nod bawah: 9 Penggantian kedudukan
17:23:45.083 [utama] INFO baris gilir.PriorityQueue - Proses penggantian [Dequeue], perbandingan nilai nod. Nod atas: 9 Nod bawah: 5 Penggantian kedudukan
17:23:45.084 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 3 Val: 3
17:23:45.084 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 10
17:23:45.084 [utama] INFO queue.PriorityQueue - [Dequeue] Kiri dan kanan kanak-kanak Bandingkan nod untuk mendapatkan nilai minimum. kiri: 5 kanan: 8
17:23:45.084 [utama] INFO baris gilir.PriorityQueue - [Dequeue] Proses penggantian, perbandingan nilai nod. Nod atas: 9 Nod bawah: 8 Penggantian kedudukan
17:23:45.084 [utama] INFO queue.PriorityQueue - Proses penggantian [Dequeue], perbandingan nilai nod. Nod atas: 8 Nod bawah: 7 Penggantian kedudukan
17:23:45.084 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 5 Val: 1
17:23:45.084 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 9
17:23:45.084 [utama] INFO queue. PriorityQueue - [Dequeue] Kiri dan kanan kanak-kanak Bandingkan nod untuk mendapatkan nilai minimum. kiri: 5 kanan: 7
17:23:45.084 [utama] INFO baris gilir.PriorityQueue - [Dequeue] Proses penggantian, perbandingan nilai nod. Nod atas: 8 Nod bawah: 7 Penggantian kedudukan
17:23:45.084 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 2 Val: 6
17:23:45.084 [utama] INFO timbunan.__test__.HeapTest - Keputusan ujian: 8
17:23:45.084 [utama] INFO queue. PriorityQueue - [Dequeue] Kiri dan kanan kanak-kanak Bandingkan nod untuk mendapatkan nilai minimum. kiri: 5 kanan: 6
17:23:45.084 [utama] INFO baris gilir.PriorityQueue - [Dequeue] Proses penggantian, perbandingan nilai nod. Nod atas: 7 Nod bawah: 6 Penggantian kedudukan
17:23:45.084 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 2 Val: 1
17:23:45.084 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 7
17:23:45.084 [utama] INFO queue. PriorityQueue - [Dequeue] Proses penggantian , perbandingan nilai nod. Nod atas: 6 Nod bawah: 5 Penggantian kedudukan
17:23:45.084 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 1 Val: 4
17:23:45.084 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 6
17:23:45.084 [utama] INFO queue. PriorityQueue - [Dequeue] Proses penggantian , perbandingan nilai nod. Nod atas: 5 Nod bawah: 4 Penggantian kedudukan
17:23:45.084 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 1 Val: 3
17:23:45.084 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 5
17:23:45.084 [utama] INFO queue. PriorityQueue - [Dequeue] Proses penggantian , perbandingan nilai nod. Nod atas: 4 Nod bawah: 3 Penggantian kedudukan
17:23:45.084 [utama] INFO queue.PriorityQueue - [Dequeue] Gantikan keputusan dan akhirnya tukar kedudukan. Idx: 1 Val: 1
17:23:45.084 [utama] timbunan INFO.__test__.HeapTest - Keputusan ujian: 4
17:23:45.084 [utama] INFO queue.PriorityQueue - [Dequeue] Keputusan penggantian , akhirnya bertukar kedudukan. Idx: 0 Val: 1
17:23:45.084 [utama] INFO timbunan.__test__.HeapTest - Keputusan ujian: 3
17:23:45.084 [utama] INFO timbunan.__test__.HeapTest - Keputusan ujian: 1

Proses selesai dengan kod keluar 0

Longgokan besar ialah hasil keluaran dalam susunan terbalik, diisih dan keluaran daripada besar ke kecil.

Longgokan ruang yang besar: [15,12,8,11,10,7,6,1,5,4,9,3,null,null,null,null,null,null,null, null ,null,null,null,null]

Pembelajaran yang disyorkan: "tutorial video java"

Atas ialah kandungan terperinci Penjelasan terperinci tentang prinsip dan pelaksanaan timbunan minimum dan timbunan maksimum struktur data Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan：
Artikel ini dikembalikan pada:jb51.net. Jika ada pelanggaran, sila hubungi admin@php.cn Padam
Artikel sebelumnya：Tutorial pembangunan laman web dinamik Web JavaArtikel seterusnya：Tutorial pembangunan laman web dinamik Web Java

Artikel berkaitan

Lihat lagi