乐趣区

关于堆:数据结构与算法堆

jiezi

前言

在学习 ScheduledThreadPoolExecutor 时，发现该线程池应用的队列为 DelayedWorkQueue，DelayedWorkQueue 是一个基于堆构造实现的延时队列和优先级队列，为了搞明确 DelayedWorkQueue 的实现，本篇文章先对堆数据结构进行学习，并且基于堆数据结构实现一个优先级队列以加深对堆数据结构的了解。

注释

一. 堆的定义

堆的定义如下所示。

  • 堆是一颗齐全二叉树；
  • 父节点的元素如果总是 大于等于 子节点，称之为大根堆；
  • 父节点的元素如果总是 小于等于 子节点，称之为小根堆。

要了解堆，首先须要理解什么是齐全二叉数。齐全二叉树定义为：如果二叉树的深度为 h，那么除第 h 层外，其余第 1 到 h - 1 层的节点数都达到最大值，第 h 层的所有节点都间断集中在右边。一颗齐全二叉树如下所示。

大根堆如下所示。

小根堆如下所示。

通常，堆中元素用一个数组来寄存。以上图的小根堆为例，节点旁边的数字代表以后节点在数组中的索引，能够发现其法则就是：依照层序遍历的形式遍历齐全二叉树，并每遍历一个节点就将以后节点的元素增加到数组中。所以上图的小根堆以数组示意如下。

最初，能够依据堆中某个节点在数组中的索引来计算这个节点的左右子节点和父节点在数组中的索引。计算的 Java 代码如下所示。

public class HeapTry {public int getLeft(int i) {return (i + 1) * 2 - 1;
    }

    public int getRigth(int i) {return (i + 1) * 2;
    }

    public int getParent(int i) {if (i == 0) {return 0;}
        return (i - 1) / 2;
    }
    
    ......

}

二. 堆的性质

  • 大根堆的性质：父节点的元素总是 大于等于 子节点。
  • 小根堆的性质：父节点的元素总是 小于等于 子节点。

以小根堆为例，思考这样一个场景：给定一个小根堆，而后将根节点的元素删除并为根节点增加一个新的元素，新的元素不满足小于等于子节点的元素，此时小根堆的性质受到毁坏。图示如下。

对于上述场景，如果须要复原小根堆的性质，则以根节点作为第一个父节点，依照如下步骤执行。

  1. 将父节点与子节点的元素进行比拟并失去元素最小的节点，如果元素最小的节点是父节点，那么曾经复原小根堆的性质，执行完结；如果元素最小的节点是某个子节点，执行步骤 2；
  2. 将父节点与元素最小的子节点调换元素，因为调换元素后子节点有可能毁坏小根堆性质，因而从子节点开始，执行步骤 1，直到复原小根堆性质。

图示如下。

将复原小根堆性质的算法用 Java 代码实现如下。

public class HeapTry {

    ......

    public void keepHeap(int[] array, int i, int size) {
        // 通过父节点计算左右子节点的数组索引
        int left = getLeft(i);
        int rigth = getRigth(i);

        // 最小节点的数组索引
        int smallest;

        // 比拟失去父节点和子节点中的最小节点的数组索引
        if (left < size) {smallest = (array[i] <= array[left]) ? i : left;
        } else {smallest = i;}
        if (rigth < size) {smallest = (array[smallest] <= array[rigth]) ? smallest : rigth;
        }

        // 如果 i 与 smallest 不相等，表明父节点不满足小于等于子节点
        // 将父节点元素与最小子节点元素进行替换
        if (i != smallest) {int temp = array[i];
            array[i] = array[smallest];
            array[smallest] = temp;
            // 递归以避免替换后子节点不满足小根堆性质
            keepHeap(array, smallest, size);
        }
    }

}

大根堆与小根堆相似，这里就不再举大根堆的例子了。

三. 堆的构建

如果给定一个数组，外面元素并没有依照堆的性质进行搁置，此时若须要依据数组中的元素构建一个堆，则应该让所有非叶子节点放弃堆的性质（叶子节点总是满足堆的性质）。曾经晓得，一个堆的叶子节点总是在数组的最初局部，因而通过计算最初一个叶子节点（即数组中的最初一个地位）的父节点，就能够失去最初一个非叶子节点，该非叶子节点往前的所有节点都是非叶子节点，所以从最初一个非叶子节点开始往前，让每一个非叶子节点放弃堆的性质，就能够构建一个堆。图示如下。

能够看到，叶子节点总是在数组的最初局部，并且通过计算最初一个叶子节点（数组索引为 5）的父节点能够失去最初一个非叶子节点（数组索引为 2）。

构建堆的 Java 代码如下所示。

public class HeapTry {

    ......

    public void createHeap(int[] array, int size) {
        // 计算最初一个非叶子节点的数组索引
        int lastParent = getParent(size - 1);

        // 从最初一个非叶子节点往前遍历每一个非叶子节点，并让每个非叶子节点放弃堆性质
        for (int i = lastParent; i >= 0; i--) {keepHeap(array, i, size);
        }
    }
    
}

四. 堆的排序

因为小根堆的根节点的元素总是整个堆中的最小元素，大根堆的根节点的元素总是整个堆中的最大元素，因而能够基于堆的性质实现排序算法（通常小根堆实现降序排序，大根堆实现升序排序）。给定一个小根堆，且一共有 n 个元素，堆排序算法步骤如下。

  1. 将小根堆的根节点与堆最初一个节点调换元素，而后执行步骤 2；
  2. 将前 n - 1 个节点从新构建一个小根堆，并且令 n =n-1，如果 n 为 0 则排序完结，否则执行步骤 1。

图解流程如下所示。

堆排序（小根堆）的 Java 代码如下所示。

public class HeapTry {

    ......

    public void heapSort(int[] array, int size) {if (size == 0) {return;}
        while (size > 0) {int temp = array[0];
            array[0] = array[size - 1];
            array[size - 1] = temp;
            createHeap(array, size - 1);
            size = size - 1;
        }
    }
    
}

五. 插入和删除

如果要基于堆实现一个优先级队列，那么堆须要可能反对插入和删除元素。首先是元素的插入，以小根堆为例，将须要插入的元素增加到堆的最初以生成最初一个叶子节点，而后将其和父节点进行比拟，如果其小于父节点则和父节点调换元素，而后持续和新地位对应的父节点进行比拟，直到插入的元素大于等于父节点或者插入的元素成为根节点的元素为止。图示如下。

而后是元素的删除，同样以小根堆为例，每次删除都应该删除堆中的最小元素，即根节点的元素，而后将堆的最初一个叶子节点的元素填充到根节点，此时填充到根节点的元素可能毁坏堆的性质，因而须要应用第二大节中的算法来复原根节点的堆的性质。图示如下。

堆的插入和删除的 Java 代码如下所示。

public class HeapTry {

    ......

    public void insert(int[] array, int size, int i) {array[size] = i;
        int index = size;
        while (array[index] < array[getParent(index)]) {int temp = array[index];
            array[index] = array[getParent(index)];
            array[getParent(index)] = temp;
            index = (index - 1) / 2;
        }
    }

    public int pop(int[] array, int size) {if (size <= 0) {throw new IndexOutOfBoundsException();
        }
        int result = array[0];
        array[0] = array[size - 1];
        array[size - 1] = 0;
        keepHeap(array, 0, size - 1);
        return result;
    }

}

六. 实现优先级队列

本大节实现的优先级队列基于大根堆进行实现。要基于堆实现优先级队列，首先须要设计队列中的元素。先给出队列元素的 Java 代码，而后再进行阐明。

public class PriObject<V> {

    private final V value;
    private final int priority;
    private final LocalDateTime dateTime;

    public PriObject(V value, int priority) {
        this.value = value;
        this.priority = priority;
        dateTime = LocalDateTime.now();}

    public V getValue() {return value;}

    public int getPriority() {return priority;}

    public LocalDateTime getDateTime() {return dateTime;}

    public int compareTo(PriObject<?> priObject) {if (priority > priObject.getPriority()) {return 1;} else if (priority < priObject.getPriority()) {return -1;} else {return -dateTime.compareTo(priObject.getDateTime());
        }
    }

}

队列元素类 PriObject 有三个属性，含意如下。

  • value 示意元素的值；
  • priority 示意元素的优先级，这里设定值越大优先级越高；
  • dateTime 示意元素的生成工夫，当向优先级队列增加 value 时，优先级队列会将 value 封装成一个 PriObject 对象，dateTime 则示意这个元素的生成工夫，用于两个元素 priority 相等时判断优先级，设定工夫越早越优先。

队列元素类 PriObject 还提供了 compareTo() 办法用于两个元素的比拟，比拟规定为：priority 越大越优先，如果 priority 相等则 dateTime 越小越优先。

上面看一下优先级队列 PriorityQueue 的字段。

public class PriorityQueue<T> {

    // 堆数组初始容量为 16
    private final int INITAIL_SIZE = 16;

    // 堆数组
    private PriObject<?>[] array = new PriObject<?>[INITAIL_SIZE];

    // 堆元素个数
    private final AtomicInteger size = new AtomicInteger(0);

    // 全局锁
    private final Lock lock = new ReentrantLock();
    
    ......
    
}

PriorityQueue的全局锁字段用于优先级队列在 offer() 元素和 poll() 元素时线程平安。

PriorityQueue外部也应用了办法来获取左右子节点和父节点的数组索引以及放弃堆性质，如下所示。

public class PriorityQueue<T> {

    ......

    private int getLeft(int i) {return (i + 1) * 2 - 1;
    }

    private int getRight(int i) {return (i + 1) * 2;
    }

    private int getParent(int i) {if (i == 0) {return 0;}
        return (i - 1) / 2;
    }

    private void keepHeap(int i, int size) {int left = getLeft(i);
        int rigth = getRight(i);

        int max;

        if (left < size) {max = (array[i].compareTo(array[left]) > 0) ? i : left;
        } else {max = i;}
        if (rigth < size) {max = (array[max].compareTo(array[rigth]) > 0) ? max : rigth;
        }

        if (i != max) {PriObject<?> temp = array[i];
            array[i] = array[max];
            array[max] = temp;
            keepHeap(max, size);
        }
    }
    
    ......
    
}

上面看一下 PriorityQueue 的offer()办法。

public class PriorityQueue<T> {

    ......

    /**
     * 增加元素到队列，每一个元素会被封装为一个 {@link PriObject} 对象
     * 而后被增加到队列中。* @param value 队列存储的元素
     * @param priority 优先级
     * @return 增加胜利返回 true，失败返回 false
     */
    public boolean offer(T value, int priority) {lock.lock();
        try {PriObject<T> pObj = new PriObject<>(value, priority);
            if (size.get() == array.length) {resize();
            }
            int index = size.get();
            array[index] = pObj;
            while (array[index].compareTo(array[getParent(index)]) > 0) {PriObject<?> temp = array[index];
                array[index] = array[getParent(index)];
                array[getParent(index)] = temp;
                index = getParent(index);
            }
            size.incrementAndGet();} catch (Exception e) {return false;} finally {lock.unlock();
        }
        return true;
    }
    
    private void resize() {
        int oldSize = array.length;
        int newSize = oldSize << 1;
        array = Arrays.copyOf(array, newSize);
    }
    
    ......
    
}

在向优先级队列增加一个元素时，如果元素个数在增加前曾经等于堆数组长度，此时会触发扩容机制，并且扩容后容量为扩容前的一倍。

上面再看一下 PriorityQueue 的poll()办法。

public class PriorityQueue<T> {

    ......

    public T poll() {
        T value;
        lock.lock();
        try {int currentSize = size.get();
            if (currentSize == 0) {return null;}
            value = (T) array[0].getValue();
            array[0] = array[currentSize - 1];
            array[currentSize - 1] = null;
            keepHeap(0, currentSize - 1);
            size.decrementAndGet();} catch (Exception e) {value = null;} finally {lock.unlock();
        }
        return value;
    }

}

最初编写测试程序来验证实现的优先级队列的性能。测试代码如下所示。

class PriorityQueueTest {

    @Test
    void givenThreeEventsWithDifferentPriority_whenOfferToPriorityQueue_thenGetEventByPriority() {Event event1 = new Event("This is Event-1");
        Event event2 = new Event("This is Event-2");
        Event event3 = new Event("This is Event-3");
        PriorityQueue<Event> priorityQueue = new PriorityQueue<>();

        priorityQueue.offer(event1, 10);
        priorityQueue.offer(event2, 20);
        priorityQueue.offer(event3, 5);

        assertThat(priorityQueue.poll().getEvent(), is("This is Event-2"));
        assertThat(priorityQueue.poll().getEvent(), is("This is Event-1"));
        assertThat(priorityQueue.poll().getEvent(), is("This is Event-3"));
        assertThat(priorityQueue.poll() == null, is(true));
    }

    @Test
    void givenThreeEventsWithSamePriority_whenOfferToPriorityQueue_thenGetEventWithFifo() {Event event1 = new Event("This is Event-1");
        Event event2 = new Event("This is Event-2");
        Event event3 = new Event("This is Event-3");
        PriorityQueue<Event> priorityQueue = new PriorityQueue<>();

        priorityQueue.offer(event1, 10);
        sleep10Millisecond();
        priorityQueue.offer(event2, 10);
        sleep10Millisecond();
        priorityQueue.offer(event3, 10);

        assertThat(priorityQueue.poll().getEvent(), is("This is Event-1"));
        assertThat(priorityQueue.poll().getEvent(), is("This is Event-2"));
        assertThat(priorityQueue.poll().getEvent(), is("This is Event-3"));
        assertThat(priorityQueue.poll() == null, is(true));
    }

    @Test
    void givenSeventeenEventsWithDifferentPriority_whenOfferToPriorityQueue_thenTriggerResize() {
        String eventString = "This is Event-";
        PriorityQueue<Event> priorityQueue = new PriorityQueue<>();

        for (int i = 0; i < 17; i++) {Event event = new Event(eventString + i);
            priorityQueue.offer(event, i);
        }

        for (int i = 16; i >= 0; i--) {assertThat(priorityQueue.poll().getEvent(), is(eventString + i));
        }
    }

    @Test
    void givenSeventeenEventsWithSamePriority_whenOfferToPriorityQueue_thenTriggerResize() {
        String eventString = "This is Event-";
        PriorityQueue<Event> priorityQueue = new PriorityQueue<>();

        for (int i = 0; i < 17; i++) {Event event = new Event(eventString + i);
            priorityQueue.offer(event, 10);
            sleep10Millisecond();}

        for (int i = 0; i < 17; i++) {assertThat(priorityQueue.poll().getEvent(), is(eventString + i));
        }
    }

    private void sleep10Millisecond() {
        try {Thread.sleep(10);
        } catch (InterruptedException e) {System.out.println(e.getMessage());
        }
    }

    private static class Event {
        private String event;

        public Event(String event) {this.event = event;}

        public String getEvent() {return event;}
    }

}

测试了四个场景，别离是：priority 不同，priority 雷同，触发扩容时 priority 不同和触发扩容时 priority 雷同这四种场景下的优先级队列的性能实现。

总结

堆是一颗齐全二叉树，并且依据父节点总是大于等于子节点或者父节点总是小于等于子节点可将堆划分为 大根堆 和小根堆。堆中元素能够由一个数组来示意，并且能够依据某个节点在数组中的索引计算失去该节点的左右子节点和父节点在数组中的索引。基于堆能够实现排序算法，通常，大根堆实现升序排序，小根堆实现降序排序。基于堆还能够实现优先级队列，并且优先级队列的元素存储在一个堆数组中，堆数组在容量满时会进行扩容，因而能够将优先级队列看作是一个无界队列。

退出移动版