Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之二叉堆

更新時(shí)間：2022年02月18日 09:58:39 作者：我是小白呀

二叉堆是一種特殊的堆，其實(shí)質(zhì)是完全二叉樹(shù)。二叉堆有兩種：最大堆和最小堆。最大堆是指父節(jié)點(diǎn)鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值。而最小堆恰恰相反，指的是父節(jié)點(diǎn)鍵值總是小于任何一個(gè)子節(jié)點(diǎn)的鍵值

概述

從今天開(kāi)始, 小白我將帶大家開(kāi)啟 Java 數(shù)據(jù)結(jié)構(gòu) & 算法的新篇章.

優(yōu)先隊(duì)列

優(yōu)先隊(duì)列 (Priority Queue) 和隊(duì)列一樣, 是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu). 優(yōu)先隊(duì)列中的每個(gè)元素有各自的優(yōu)先級(jí), 優(yōu)先級(jí)最高的元素最先得到服務(wù). 如圖:

二叉堆

二叉堆 (Binary Heap) 是一種特殊的堆, 二叉堆具有堆的性質(zhì)和二叉樹(shù)的性質(zhì). 二叉堆中的任意一節(jié)點(diǎn)的值總是大于等于其孩子節(jié)點(diǎn)值. 如圖:

二叉堆實(shí)現(xiàn)

獲取索引

// 獲取父節(jié)點(diǎn)的索引值
public int parent(int index) {
    if (index <= 0) {
        throw new RuntimeException("Invalid Index");
    }

    return (index - 1) / 2;
}

// 獲取左孩子節(jié)點(diǎn)索引
public int leftChild(int index) {
    return index * 2 + 1;
}

// 獲取右孩子節(jié)點(diǎn)索引
public int rightChild(int index) {
    return index * 2 + 2;
}

添加元素

// 添加元素
public void add(E e) {
    data.add(e);
    siftUp(data.size() - 1);
}

siftUp

// siftDown
private void siftDown(int k) {
    while (leftChild(k) < data.size()) {
        int j = leftChild(k);
        if (j + 1 < data.size() && data.get(j + 1).compareTo(data.get(j)) > 0) {
            j++;
        }
        if (data.get(k).compareTo(data.get(j)) >= 0) {
            break;
        }
        Collections.swap(data, k, j);
        k = j;
    }
}

完整代碼

import java.util.ArrayList;
import java.util.Collections;

public class BinaryHeap<E extends Comparable<E>> {

    private ArrayList<E> data;

    // 無(wú)參構(gòu)造
    public BinaryHeap() {
        data = new ArrayList<>();
    }

    // 有參構(gòu)造
    public BinaryHeap(int capacity) {
        data = new ArrayList<>(capacity);
    }

    // 或者元素個(gè)數(shù)
    public int size() {
        return data.size();
    }

    // 判斷堆是否為空
    public boolean isEmpty() {
        return data.isEmpty();
    }

    // 獲取父節(jié)點(diǎn)的索引值
    public int parent(int index) {
        if (index <= 0) {
            throw new RuntimeException("Invalid Index");
        }

        return (index - 1) / 2;
    }

    // 獲取左孩子節(jié)點(diǎn)索引
    public int leftChild(int index) {
        return index * 2 + 1;
    }

    // 獲取右孩子節(jié)點(diǎn)索引
    public int rightChild(int index) {
        return index * 2 + 2;
    }

    // 添加元素
    public void add(E e) {
        data.add(e);
        siftUp(data.size() - 1);
    }

    // siftUp
    private void siftUp(int k) {
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
            Collections.swap(data, k, parent(k));
            k = parent(k);
        }

    }

    // siftDown
    private void siftDown(int k) {
        while (leftChild(k) < data.size()) {
            int j = leftChild(k);
            if (j + 1 < data.size() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j++;
            }
            if (data.get(k).compareTo(data.get(j)) >= 0) {
                break;
            }
            Collections.swap(data, k, j);
            k = j;
        }
    }
}

到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之二叉堆的文章就介紹到這了,更多相關(guān)Java 二叉堆內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: