Hello, I'm Monday.

We talked last time Heap and heap sorting This time, let's talk about heap related topics.

1, Almost ordered array sorting

1. Title Description:

An almost ordered array is known, which means that if the array is arranged in order, the distance of each element must not exceed K, and K is relatively small relative to the length of the array.

Please select an appropriate sorting strategy to sort this array.

2. Solution:

Starting with the first number,

Put the first K+1 number into the small root heap, pop up the first number and put it in the first position of the array;

Put the K+2 number into the small root heap, and then pop up the first number and put it in the second position of the array;

Put the K + 3rd number into the small root heap, and then pop up the first number and put it in the third position of the array;

Until the small root heap is empty

3. Detailed reference code:

    public static void sortArrayDistanceLessK(int[] arr, int k) {
        if (arr == null || arr.length < 2 || k == 0) {
            return;
        }

        // The default is small root heap
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        // Marks the array subscript of the element currently placed in the heap
        int index = 0;
        // Put the first k numbers into the array
        for (; index < k; index++) {
            heap.add(arr[index]);
        }
        // Marks the ordered subscripts in the current array
        int i = 0;
        // From the k+1 number to the last number of the array,
        for (; index < arr.length; index++) {
            // One number at a time,
            heap.add(arr[index]);
            // At the same time, pop up. At this time, put the heap top element into the array, and move the sorting subscript back
            arr[i++] = heap.poll();
        }
        // Put the remaining data in the small root heap into the array
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }

4. Time complexity is O(N*logK)

There are only K+1 numbers in the heap, that is, the process of adjusting to a small root heap. The time complexity is logK. Because the entire array needs to be traversed, the final time complexity is O(N*logK).

2, Maximum line segment coincidence problem

1. Title Description:

Given many line segments, each line segment has two numbers [start, end], indicating the start position and end position of the line segment, and the left and right are closed intervals.

regulations:

1) The start position and end position of the line segment must be integers

2) Definition of two line segment coincidence: the length of the line segment coincidence area must be > = 1 to indicate that the line segment coincides

Calculation: the coincident area with the most segments contains several segments.

2. Solution:

1) Sort all line segments from small to large according to the starting position, and prepare a small root heap for storing the end position of line segments

2) Traverse all the sorted line segments, pop up the number less than or equal to the starting position of the line segment in the small root pile, and put the number of the ending position of the line segment in the small root pile. At this time, the number of small root piles is the number of line segments contained in the reconnection area from the starting position of the line segment as the left boundary of the coincidence area. (the left boundary of any coincident area must be the left boundary of a line segment)

Because the number in the small root heap indicates that the right boundary of the previous line segment will pass through the left boundary of the current line segment, and the left boundary of the previous line segment is smaller than the left boundary of the current line segment, the number of small root heap is the number of line segments contained in the coincidence area.

3) Finally, the maximum number in step 2 is the number of segments contained in the coincident area with the most segments

3. Detailed reference code:

    public static class Line {
        private int start;
        private int end;

        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    /**
     * Time complexity O(N*logN)
     */
    public static int lineCoverMaxByHeap(int[][] n) {
        Line[] lines = new Line[n.length];
        for (int i = 0; i < n.length; i++) {
            lines[i] = new Line(n[i][0], n[i][1]);
        }
        // Sort all segments from small to large according to the starting subscript
        Arrays.sort(lines, (o1, o2) -> o1.start - o2.start);
        // Prepare a small root heap (store the end value of the line segment)
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int cover = 0;
        for (Line line : lines) { // O(N)
            // Pop up all data less than or equal to the starting value of the current line segment in the small root heap
            while (!heap.isEmpty() && heap.peek() <= line.start) { // O(logN)
                heap.poll();
            }
            // Put the end value of the current line segment into the small root heap
            heap.add(line.end);
            cover = Math.max(cover, heap.size());
        }
        return cover;
    }

All codes: https://github.com/monday-pro/algorithm-study/tree/master/src/basic/heap