Skip to content

heap

堆(heap)是一种满足特定条件的完全二叉树,主要可分为两种类型:

  • 小顶堆(min heap):任意节点的值<=其子节点的值。
  • 大顶堆(max heap):任意节点的值>=其子节点的值。

堆的常用操作包括插入、删除和堆化等。堆通常用于实现优先队列(priority queue), 在图论中的Dijkstra算法和贪心算法中的Huffman编码等场景中也有广泛应用。

堆和优先队列是一样的

java
package com.jasper;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 小顶堆:任意一个字节点的值<=其父节点的值 <br/>
 * 大顶堆:任意一个字节点的值>=其父节点的值
 *
 */
public class PriorityQueueDemo {
    public static void main(String[] args) {
        final PriorityQueue<Integer> minHeap = new PriorityQueue<>(Arrays.asList(1,3,2,4,5));
        final PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap.offer(1);
        maxHeap.offer(3);
        maxHeap.offer(2);
        maxHeap.offer(5);
        maxHeap.offer(4);

        final Integer peek = maxHeap.peek();
        System.out.println("max peek = " + peek);
        final Integer peek1 = minHeap.peek();
        System.out.println("min peek = " + peek1);

        final int size = maxHeap.size();
        System.out.println("max size = " + size);

        while (!maxHeap.isEmpty()){
            final Integer poll = maxHeap.poll();
            System.out.println("poll = " + poll);
        }
        while (!minHeap.isEmpty()){
            final Integer poll = minHeap.poll();
            System.out.println("poll = " + poll);
        }
    }
}

heapify 堆化

堆化操作是指将一个无序的数组构造成一个堆的过程。堆化可以分为自顶向下堆化和自底向上堆化两种方法。