Data structures and algorithms - heaps

preface

In learning ScheduledThreadPoolExecutor found the thread pool use queue for DelayedWorkQueue, DelayedWorkQueue is a heap structure based implementation of delay queues and priority queues, In order to understand the DelayedWorkQueue implementation, this article first learns about the heap data structure and implements a priority queue based on the heap data structure to deepen the understanding of the heap data structure.

The body of the

Definition of heap

The definition of the heap is shown below.

The heap is a complete binary tree;
If the element of the parent node is alwaysGreater than or equal toChild nodes, called the large root heap;
If the element of the parent node is alwaysLess than or equal toThe child node, called the small root heap.

To understand heaps, you first need to understand what a complete binary number is. A complete binary tree is defined as: if the depth of the binary tree is h, then the number of nodes from layers 1 to h-1 reaches the maximum except for layer h, and all nodes of layer h are contiguously concentrated on the left. A complete binary tree is shown below.

The large root heap is shown below.

The small root heap is shown below.

Typically, the elements in the heap are stored in an array. For example, the number next to the node represents the index of the current node in the array. It can be found that the rule is to traverse the complete binary tree in the way of hierarchical traversal, and add the elements of the current node to the array after traversal of a node. So the small root heap in the figure above is represented as an array like this.

Finally, you can calculate the index of the left and right children of a node in the heap and the index of the parent node in the array based on the index of the node in the heap. The Java code for the calculation is shown below.

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; }... }

II. The nature of the heap

Property of the large root heap: the elements of the parent node are alwaysGreater than or equal toChild nodes.
Property of small root heap: the element of the parent node is alwaysLess than or equal toChild nodes.

Taking the small root heap as an example, consider a scenario where, given a small root heap, the element of the root node is removed and a new element is added to the root node. The new element does not satisfy the element less than or equal to the child node, and the properties of the small root heap are broken. The diagram is shown below.

For the above scenario, if you need to restore the nature of the small root heap, follow these steps with the root node as the first parent node.

The parent node is compared with the elements of the child node and the node with the smallest element is obtained. If the node with the smallest element is the parent node, then the nature of small root heap has been restored and the execution is over. If the smallest element node is a child node, perform step 2;
The parent node swaps elements with the smallest child node of the element. Since the child node may break the small root heap property after the element is exchanged, step 1 is performed from the child node until the small root heap property is restored.

The diagram is shown below.

The algorithm to restore the small root heap nature is implemented in Java code as follows.

public class HeapTry { ...... Public void KeepHeap (int[] Array, int I, int size) {public void KeepHeap (int[] Array, int I, int size) { int rigth = getRigth(i); // Smallest index of an array of nodes; // Smallest = (array[I] <= array[left])? i : left; } else { smallest = i; } if (rigth < size) { smallest = (array[smallest] <= array[rigth]) ? smallest : rigth; } // If I is not equal to a line, which is an example, the parent node is not equal to the child node. = smallest) { int temp = array[i]; array[i] = array[smallest]; array[smallest] = temp; // Recursive to avoid swapping child nodes that do not satisfy the small root heap property keepHeap(array, smallest, size); }}}

The large root heap is similar to the small root heap, so I won’t use the large root heap example here.

3. Heap construction

If you are given an array whose elements are not placed as heap, and you need to build a heap from the elements in the array, you should have all non-leaf nodes behave as heap (leaf nodes always behave as heap). Already know, a pile of leaf node is always at the end of the array, so by computing the last leaf node (i.e., the final location of the array) of the parent node, you can get the final a leaf node, this not the leaf node and all nodes are leaf nodes, so since the last the leaf node, You can build a heap by keeping each non-leaf node as a heap. The diagram is shown below.

As you can see, the leaf node is always at the end of the array, and the last non-leaf node (array index 2) can be obtained by calculating the parent of the last leaf node (array index 5).

The Java code to build the heap is shown below.

public class HeapTry { ...... Public void createHeap(int[] Array, int size) {int lastParent = getParent(size-1); For (int I = lastParent; int I = lastParent; int I = lastParent; i >= 0; i--) { keepHeap(array, i, size); }}}

4. Heap sorting

Since the element of the root node of the small root heap is always the smallest element in the whole heap, and the element of the root node of the large root heap is always the largest element in the whole heap, the sorting algorithm can be implemented based on the properties of the heap (usually the small root heap is sorted in descending order, and the large root heap is sorted in ascending order). Given a small root heap with a total of n elements, the heap-sorting algorithm steps as follows.

Switch elements between the root node of the small root heap and the last node of the heap, and then perform step 2;
The first n-1 nodes are rebuilt into a small root heap, and n=n-1. If n is 0, the sort is finished. Otherwise, step 1 is performed.

The diagram flow is shown below.

The Java code for heap sort (small root heap) is shown below.

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

V. Insert and Delete

If you want to implement a priority queue based on the heap, then the heap needs to be able to support inserting and deleting elements. First is the insertion of the element. Take the small root heap as an example, the element that needs to be inserted is added to the end of the heap to generate the last leaf node, and then it is compared with the parent node. If it is smaller than the parent node, the element is exchanged with the parent node, and then the comparison is continued with the parent node corresponding to the new position. Until the inserted element is greater than or equal to the parent node or the inserted element becomes the element of the root node. The diagram is shown below.

Then delete elements, the same small root stacks, for example, every time delete should be deleted in the heap minimum elements, namely the root node of the element, and then the last leaf nodes of the heap element filling to the root node, the filling to the root node of the element may damage the nature of the heap, so you need to use the algorithm to recover in the second section of the root node of the heap. The diagram is shown below.

The Java code for the heap insert and delete is shown below.

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

VI. Implement priority queue

The priority queue implemented in this section is implemented based on the large root heap. To implement a priority queue based on the heap, you first need to design the elements in the queue. I’ll show you the Java code for the queue elements, and then I’ll explain it.

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

The queue element class PriObject has three attributes that mean the following.

Value represents the value of an element;
Priority represents the element’s priority, where the higher the value, the higher the priority.
The dateTime represents the generation time of the element, and when a Value is added to the priority queue, the priority queue encapsulates the Value into onePriObjectObject, dateTime represents the creation time of this element, and is used to determine the priority of two elements with the same priority.

The queue element class PriObject also provides a compareTo() method for comparing two elements. The compareTo() method is used to compare two elements with a higher priority, or a lower dateTime if the priority is equal.

Let’s take a look at the fields of PriorityQueue.

Public class PriorityQueue<T> {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(); . }

The global lock field of PriorityQueue is used for priority queues to be thread-safe on offer() and poll() elements.

There are also methods inside PriorityQueue to get the array index of the left and right child and parent nodes and to preserve the heap nature, as shown below.

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

Take a look at PriorityQueue’s offer() method.

public class PriorityQueue<T> { ...... /** * Add elements to the queue. Each element is wrapped as a {@link Priobject} object * and added to the queue. * @Param value (); * @Param priority (); * @Param value (); * @Param priority (); 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); }... }

When an element is added to the priority queue, if the number of elements is equal to the size of the heap array before the addition, a capacity enlargement mechanism is triggered, and the capacity after the expansion is doubled.

Let’s take a look at the poll() method of PriorityQueue.

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

Finally, write a test program to verify the function of the priority queue. The test code is shown below.

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

}

Four scenarios were tested: different priority, same priority, different priority when capacity expansion is triggered, and same priority when capacity expansion is triggered.

conclusion

The heap is a complete binary tree and can be divided into large root heaps and small root heaps based on the fact that the parent node is always greater than or equal to the children or that the parent node is always less than or equal to the children. The elements in the heap can be represented by an array, and the index of the left and right children of a node and the index of the parent node in the array can be calculated from the index of the node in the array. The sorting algorithm can be implemented based on the heap. In general, the large root heap can be sorted in ascending order and the small root heap can be sorted in descending order. The priority queue can also be implemented based on the heap, and the elements of the priority queue are stored in a heap array that expands when the heap array is full, so the priority queue can be considered an unbounded queue.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Data structures and algorithms – heaps