堆在邏輯上一棵完全二叉樹，所以可以通過數組進行數據存儲，而其余的樹大多采用鏈式結構進行數據存儲

堆分類：

大頂堆：大頂堆就是無論在任何一棵(子)樹中，父節點都是最大的

小頂堆：小頂堆就是無論在任何一棵(子)樹中，父節點都是最小的

堆的兩種操作：

上浮：一般用于向堆中添加新元素后的堆平衡

下沉：一般用于取出堆頂并將堆尾換至堆頂后的堆平衡

堆排序：利用大頂堆和小頂堆的特性，不斷取出堆頂，取出的元素就是堆中元素的最值，然后再使堆平衡

下面的文章以大頂堆為例，拿Java實現堆的各種操作。

1.MaxHeap

大頂堆：對于任一個(子)堆，堆頂最大

// 這里Comparable保證所有結點可比，是成堆基礎

public class MaxHeap >{

// 完全二叉樹，排列整齊(相當于一層一層放入)，可以用數組存儲

private ArrayList data;

public MaxHeap(int capcity){

data = new ArrayList<>(capcity);

}

public MaxHeap(){

data = new ArrayList<>();

}

// 堆是否為空

public boolean isEmpty(){

return data.isEmpty();

}

// 堆中元素個數

public int size(){

return this.data.size();

}

//......

}

復制代碼

2.操作一：獲取父/子節點

parent()

// 返回idx位置元素的父節點

// 注：這里從0放起(parent = (i - 1)/2 )，若是從1放起(parent = i / 2)

private int parent(int idx){

if (idx == 0) {

throw new IllegalArgumentException("index-0 doesn't have parent");

}

return (idx - 1) / 2;

}

復制代碼

leftChild() / rightChild()

// 返回idx位置元素的孩子節點

// 注：這里從0放起

private int leftChild(int idx){

// 若從1放起，leftChild = idx * 2

return idx * 2 + 1;

}

private int rightChild(int idx){

// 若從1放起，rightChild= idx * 2 + 1

return idx * 2 + 2;

}

復制代碼

2.操作二：添加元素

add()

將元素放到堆尾，即數組最后一個元素

加入到最后了，上浮

public void add(E e){

data.add(e);

// 傳入需要上浮的索引

siftUp(data.size() - 1);

}

復制代碼

siftUp()

上浮：子節點與(小于自己的)父節點交換

Time：O(logn)，獲取parent是不斷二分(/2) 的

private void siftUp(int k){

// 只要是父節點(data[parent]) 比 子節點(data[k])小，就進行交換

while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {

// 1.交換數組中位置

// 注：這里是

Collections.swap(k, parent(k));

// 2.更新子節點，進行下一輪上浮

// 注：也可以data.set進行三步走

k = parent(k);

}

}

復制代碼

3.操作三：取出堆頂(最大元素)

extractMax()

取出堆頂

拿到堆頂元素

刪除堆頂

將堆頂(0)與堆尾(size-1)交換，因為要產生新堆頂

刪除堆尾

堆頂下沉

public E extractMax(){

// 1.獲取堆頂元素

E ret = findMax() ;

// 2.1 將堆頂換到堆尾

Collections.swap(0, data.size() - 1);

// 2.2 刪除堆尾

data.remove(data.size() - 1);

// 2.3 下沉堆頂

siftDown(0):

return ret;

}

復制代碼

findMax()

獲取堆中最大元素

public E findMax(){

if (data.size() == 0) {

throw new IllegalArgumentException("Can not findMax when heap is empty");

}

// 堆頂最大 = 數組第一個元素(0)

return data.get(0);

}

復制代碼

siftDown()

堆頂下沉：與左右子節點較大值(且大于自己的)節點進行交換

Time：O(logn)，獲取Child是不斷二分(/2) 的

private void siftDown(int k){

// 1.判斷當前節點是否有子節點。下沉到葉節點，就沒有兒子了，就不用下沉了

// 注：因為leftChild索引肯定比rightChild小，所以只要有leftChild就有子節點

while (leftChild(k) < data.size()) {

// 2.拿到leftChild與rightChild的大值

int j = leftChild(k);

if (j + 1 < data.size() && data.get(j + 1).compareTo(data.get(j)) > 0) {

j = rightChild(k);

}

// 3.判斷子節較大值是否大于自己(父節點)

if (data.get(k).compareTo(data.get(j)) >= 0) {

break;

}

// 4.若大于，交換數組中兩節點位置

Collections.swap(k, j);

// 更新父節點，進行下一輪下沉

k = j;

}

}

復制代碼

4.操作四：數組構造堆

思路一：將已知數組一個一個加入到堆中 ====> Time = O(n*logn)

思路二：從第倒數一個非葉子節點開始下沉 ====> Time = O(n)

// 構造函數中傳入要構造成堆的數組

public MaxHeap(E[] arr){

// 注：這里數組不能直接作為ArrayList參數，要先包裝成List

data = new ArrayList<>(Arrays.asList(arr));

// 確定倒數第一個非葉子結點：最后一個葉子(length - 1)的父節點 ((i - 1)/ 2)

for (int i = parent(arr.length - 1); i >= 0; i--) {

// 逐個下沉

siftDown(i);

}

}

復制代碼

=> 驗證最大堆

在看堆排序前，我們先來驗證我們寫的代碼是否正確的。思路是，向堆中添加一百萬個隨機數，然后依次取頂取出放入到一個數組中，最后驗證看是否從大到小排列的：

public class Test{

public static void main(String[] args){

int n = 10000000;

MaxHeap heap = new MaxHeap<>();

Random random = new Random();

// 1.向堆中添加一百萬個隨機數

for (int i = 0; i < n; i++)

heap.add(random.nextInt(Integer.MAX_VALUE));

// 2.不斷從最大堆中取出堆頂 --> 從大到小

int[] arr = new int[n];

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

arr[i] = heap.extractMax();

}

// 3.驗證取出的元素是否按照從大到小排列

for (int i = 0; i < n - 1; i++)

if (arr[i] < arr[i + 1])

throw new IllegalArgumentException("Error");

System.out.println("Test MaxHeap Success!");

}

}

復制代碼

這里其實也可以直接創建出一個數組，然后構造成最大堆，再不斷取頂。相信經過上面的示例，你已經看到了堆有進行排序的能力。

==> 堆排序

堆排序原理：簡而言之，就是利用大頂堆和小頂堆的特性，不斷取出堆頂(堆中元素的最值)，然后再使堆平衡。

構建最大堆：借鑒上面構建堆的思路，從最后一個不是葉子節點的節點開始下沉

取出堆頂：不是真取出，而是通過交換堆頂(arr[0])到堆尾(arr[i])實現出堆頂 ==> 大頂堆的排序結果是從小到大

新堆再平衡：由于上一步已經將堆尾換到了堆首，所以直接再下沉就行

注意：這里采取的是數組從0開始放，即 idx 位置的 parent = idx / 2，leftChild = idx * 2，rightChild = idx * 2 + 1

public class HeapSort{

public void sort(int[] arr){

int length = arr.length;

// 1.構建最大堆：從最后一個不是葉子節點的節點開始下沉

// i=(length-1)/2，表示獲取最后一個葉子節點的父親，即最后一個不是葉子節點的節點

for (int i = (length - 1) / 2; i >= 0; i--) {

siftDown(arr,length, i);

}

for (int i = length - 1; i > 0; i--) {

// 2.取出堆頂：通過交換堆頂(arr[0])到堆尾(arr[i])，實現出堆頂

swap(arr, 0, i);

// 3.新堆再平衡：上一步已經將堆尾換到了堆首，所以直接再下沉就行

// 注：可以看到這里新堆的長度變成了i(比之前少了1)

siftDown(arr, i, 0);

}

}

private void siftDown(int[] arr, int length, int idx){

// 下沉到葉節點，就沒有兒子了，就不用下沉了

// 這里用的leftChild(2*idx)，因為如果左兒子都超過length了，右兒子也一定超過了

while (2 * idx < length) {

// 判斷左兒子和右兒子哪個大

int j = 2 * idx;

if (j + 1 < length && arr[j+1] > arr[j])

j++; // 如果右兒子大，就j++

// 判斷父親是否比兒子大

if (arr[idx] >= arr[j])

break;

// 父親小于兒子，那么就交換父子

swap(arr, idx, j);

// 更新父親idx，繼續去下一棵子樹判斷下沉

idx = j;

}

}

private void swap(int[] arr, int idx1, int idx2){

int t = arr[idx1];

arr[idx1] = arr[idx2];

arr[idx2] = t;

}

}

復制代碼

另外，如果對其他排序感興趣的同學，可以參考這篇文章 圖解十大排序算法及Java實現(詳細)...

5.操作五：取出堆頂，再加入一個元素

思路一：取出堆頂(extractMax)，然后再加入一元素(add) ====> 2 * O(logn)

思路二：將堆頂直接修改，然后下沉 ====> O(logn)

replace()

public E replace(E e){

// 1.獲取堆頂元素

E ret = findMax();

// 2.修改堆頂，即數組0位置

data.set(0, e);

// 3.下沉

siftDown(0);

return ret;

}

復制代碼

完整代碼

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

public class MaxHeap >{

private ArrayList data;

public MaxHeap(int capcity){

data = new ArrayList<>(capcity);

}

public MaxHeap(){

data = new ArrayList<>();

}

public MaxHeap(E[] arr){

data = new ArrayList<>(Arrays.asList(arr));

for (int i = parent(arr.length - 1); i >= 0; i--) {

siftUp(i);

}

}

// 堆是否為空

public boolean isEmpty(){

return data.isEmpty();

}

// 堆中元素個數

public int size(){

return this.data.size();

}

// 返回idx位置元素的父節點

// 注：這里從0放起(parent = (i - 1)/2 )，若是從1放起(parent = i / 2)

private int parent(int idx){

if (idx == 0) {

throw new IllegalArgumentException("index-0 doesn't have parent");

}

return (idx - 1) / 2;

}

// 返回idx位置元素的孩子節點

// 注：這里從0放起

private int leftChild(int idx){

// 若從1放起，leftChild = idx * 2

return idx * 2 + 1;

}

private int rightChild(int idx){

// 若從1放起，leftChild = idx * 2

return idx * 2 + 2;

}

// 添加元素

public void add(E e){

data.add(e);

siftUp(data.size() - 1);

}

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);

}

}

// 獲取堆中最大元素

public E findMax(){

if (data.size() == 0) {

throw new IllegalArgumentException("Can not findMax when heap is empty");

}

// 堆頂最大，

return data.get(0);

}

public E extractMax(){

E ret = findMax() ;

Collections.swap(data, 0, data.size() - 1);

data.remove(data.size() - 1);

siftDown(0);

return ret;

}

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 = rightChild(k);

}

if (data.get(k).compareTo(data.get(j)) >= 0) {

break;

}

Collections.swap(data, k, j);

k = j;

}

}

public E replace(E e){

E ret = findMax();

data.set(0, e);

siftDown(0);

return ret;

}

}

復制代碼

最后，對堆在Java中的應用感興趣的同學看看 PriorityQueue 的源碼，它就是通過小頂堆實現的，這里放個傳送門 【Java集合源碼】PriorityQueue源碼分析。

總結

以上是生活随笔為你收集整理的java 二叉堆_【数据结构】二叉堆：Java实现最大堆及堆排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。