K-way 병합 정렬(실전 전투)에 대한 자세한 설명

소개:

사실 K-way 병합 정렬은 여전히 ​​매우 유용합니다. 가장 간단한 방법은 TB 수준의 데이터(TB 수준 검색 키워드라고 가정)와 같은 대량의 데이터를 정렬하려고 한다고 가정하는 것입니다. ), 하지만 우리의 메모리는 GB 수준에 불과합니다. 모든 데이터를 한 번에 로드하여 정렬할 수는 없지만 결국 결과를 원하므로 어떻게 해야 할까요? K-way 병합 정렬은 실제로 "분할 및 정복" 아이디어입니다. 우리는 Q 숫자를 정렬하고 싶지만 지금은 Q를 k로 나눌 수 없습니다. 그룹, 각 그룹은 n입니다. 숫자(k

분석:

(1) k개의 정렬된 배열을 병합하는 방법은 무엇입니까?

앞서 힙에 대해 논의했기 때문에 당연히 힙의 정렬 효율성이 매우 높기 때문에 자연스럽게 힙을 사용하여 구현하는 것을 고려합니다. 오름차순으로 정렬해야 하기 때문에 최소한의 힙을 만듭니다. 최종 정렬 결과의 숫자는 항상 앞쪽이 작고 뒤쪽이 크기 때문에 모든 n 배열의 첫 번째 요소(최소 개수)를 최소 힙에 넣는 것을 고려하므로 최소 힙의 크기는 k 입니다. 이러한 방식으로 힙 구조를 조정하면 첫 번째 요소는 min(min(array1),min(array2)....min(arrayn))입니다. 이는 분명히 모든 숫자 중에서 가장 작은 요소입니다.

(2) 모든 배열은 오름차순으로 정렬되므로 힙에서 최소 요소를 삭제하면 구멍을 채울 요소를 찾아야 합니다. 이렇게 하려면 배열에서 삭제된 요소가 있는 다음 요소를 찾아 힙에 채워야 합니다. (이것은 나라에서 가장 정예인 군인을 모집하여 정예 연대에 참여시키는 것과 약간 비슷합니다. 그러면 각 연대에서 가장 강한 병사가 모집됩니다. 만약 이 사람이 전투에서 불행하게도 죽으면, 그 사람 다음으로 두 번째인 사람을 찾으십시오. 동일한 연대. 엘리트 그룹의 가장 높은 전투 효율성을 항상 유지하기 위해 이 엘리트 그룹을 계속 지원합니다) 그러면 삭제된 힙 요소를 기반으로 삭제된 힙 요소가 위치한 배열을 찾는 방법은 무엇입니까? 이를 위해서는 현재 값과 현재 값이 있는 배열의 ID를 모두 포함하는 새로운 복합 유형을 생성해야 합니다.

(3) 정렬된 각 배열은 가장 작은 요소가 지속적으로 손실되므로 정렬되지 않은 값이 점차 줄어들기 때문에 아직 정렬되지 않은 각 배열의 현재 위치를 유지하는 길이 k의 배열을 유지해야 합니다. 배열에 남아 있는 가장 작은 요소가 힙에 추가되면 현재 위치를 뒤로 이동해야 합니다.

(4) 각 배열의 현재 위치가 뒤로 이동하면 결국 배열의 끝에 도달하게 됩니다. 이때 배열은 더 이상 숫자를 제공할 수 없습니다. (이는 정상입니다. 예를 들어 샵이 있습니다. 군대의 칼 중대에는 가장 뛰어난 사람들이 포함되어 있기 때문에 최종적으로 정예 그룹이 선정되면 항상 이 중대에서 선발되며 이 중대는 결국 아무도 없어야 하므로 찾을 수 없습니다. 현재 삭제된 번호가 있는 배열에서 다음 값을 선택해야 합니다. 이때 값이 있는 다음 배열 ID를 선택하고 해당 최소값을 선택해야 합니다. 방법은 arrayIdForDeletedData = (arrayIdForDeletedData + 1) % k입니다.

(5) 결국 모든 배열 위치가 끝에 도달했습니다. 즉 모든 배열은 정렬에 관련되지 않은 값을 제공할 수 없으므로 이때 현재 힙이 비어 있는지 여부를 확인해야 합니다. 그렇지 않으면 n*k에서 가장 큰 숫자가 포함됩니다. 가장 작은 순서로 가장 큰 숫자를 출력하기 위해 deleteMin()을 수행합니다. 현재 힙이 이미 비어 있으면 루프에서 직접 뛰어내립니다.

따라서 최종 시간 복잡도는 O(n*logk)

코드:

위의 주요 기술적 세부 사항을 고려한 후에 여기 코드는 작성하기 쉽습니다.

먼저 정수를 캡슐화하는 값 객체와 그 정수가 나오는 배열을 정의합니다.

package com.charles.algo.kwaymerge;
/**
 *
 * 这个对象表明是一个可以跟踪来自于哪个数组的数据对象
 * @author charles.wang
 *
 */
public class TrackableData { 
    //data表明具体的值
    private int data;
    //comeFromArray表明这个值来自于哪一个数组
    private int comeFromArray;
 
    public TrackableData(int data,int comeFromArray){
        this.data = data;
        this.comeFromArray=comeFromArray;
    }
 
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public int getComeFromArray() {
        return comeFromArray;
    }
    public void setComeFromArray(int comeFromArray) {
        this.comeFromArray = comeFromArray;
    }
}

그런 다음 문제 해결의 핵심인 최소 힙을 정의합니다. 위에서 언급한 값 개체여야 합니다. 힙에 넣고 힙을 조정하면 이를 기반으로 한 계산이 모두 값 개체의 데이터 필드입니다.

package com.charles.algo.kwaymerge;
/**
 * @author charles.wang
 *
 */
public class MinHeap {
    // 最小堆的存储是一个数组,并且为了计算，我们第一个位置不放内容
    private TrackableData[] data;
    // 堆的大小
    private int heapSize;
    // 当前元素的数量
    private int currentSize;
    public MinHeap(int maxSize) {
        heapSize = maxSize;
        // 创建一个比最大容纳数量多1的数组的作用是启用掉数组的头元素，为了方便运算，因为从1开始的运算更加好算
        data = new TrackableData[heapSize + 1];
        currentSize = 0;
    }
    /**
     * 返回当前的堆是否为空
     * @return
     */
    public boolean isEmpty(){  
        if(currentSize==0)
            return true;
        return false;
    }
    /**
     * 这里考察堆的插入，因为最小堆内部结构中数组前面元素总是按照最小堆已经构建好的，所以我们总从尾部插入 解决方法是： Step
     * 1:先把当前的元素插入到数组的尾部 Step 2:递归的比较当前元素和父亲节点元素， Step
     * 3:如果当前的元素小于父亲节点的元素，那么就把当前的元素上移，直到移不动为止
     *
     * @param value
     * @return
     */
    public MinHeap insert(TrackableData value) {
        // 首先判断堆是否满了，如果满了就无法插入
        if (currentSize == heapSize)
            return this;
        // 如果堆还没有满，那么说明堆中还有位置可以插入，我们先找到最后一个可以插入的位置
        // currentPos表示当前要插入的位置的数组下标
        int currentPos = currentSize + 1;
        // 先插入到当前的位置，因为是从1开始的，所以数组下标运算也要+1
        data[currentPos] = value;
        // 然后比较当前元素和他的父亲元素
        // 当前元素是data[currentPos] ，父亲元素是 data[(currentPos/2],一直遍历到根
        TrackableData temp;
        // 如果currentPos为1，表明是插入的堆中第一个元素，则不用比较
        // 否则， 如果插了不止一个元素，则用插入位置的元素和其父元素比较
        while (currentPos > 1) {
            // 如果当前元素小于父亲元素，那么交换他们位置
            if (data[currentPos].getData() < data[currentPos / 2].getData()) {
                temp = data[currentPos / 2];
                data[currentPos / 2] = data[currentPos];
                data[currentPos] = temp;
                // 更新当前位置
                currentPos = currentPos / 2;
            }
            // 否则， 在假定已有的堆是最小堆的情况下，说明现在插入的位置是正确的，不用变换
            else {
                break;
            }
        }
        // 插入完毕之后，吧当前的堆中元素的个数加1
        currentSize++;
        return this;
    }
    /**
     * 这里考察堆的删除 因为是最小堆，所以肯定删除最小值就是删除堆的根元素，此外，还必须要调整剩余的堆使其仍然保持一个最小堆
     * 因为有删除最小元素之后最小元素位置就有了个空位，所以解决方法是： Step 1:吧堆中最后一个元素复制给这个空位 Step
     * 2:依次比较这个最后元素值，当前位置的左右子元素的值，从而下调到一个合适的位置 Step 3:从堆数组中移除最后那个元素
     */
    public TrackableData deleteMin() {
        // 如果最小堆已经为空，那么无法删除最小元素
        if (currentSize == 0)
            return null;
        // 否则堆不为空，那么最小元素总是堆中的第一个元素
        TrackableData minValue = data[1];
        // 既然删除了最小元素，那么堆中currentSize的尺寸就要-1，为此，我们必须为数组中最后一个元素找到合适的新位置
        // 堆中最后一个元素
        TrackableData lastValue = data[currentSize];
        // 先将堆中最后一个元素移动到最小堆的堆首
        data[1] = lastValue;
        // 把堆内部存储数组的最后一个元素清0
        data[currentSize] = null;
        // 并且当前的堆的尺寸要-1
        currentSize--;
        // 现在开始调整堆结构使其仍然为一个最小堆
        int currentPos = 1; // 当前位置设置为根，从根开始比较左右
        int leftPos = currentPos * 2;
        TrackableData leftValue;
        TrackableData rightValue;
        TrackableData temp;
        // 如果左位置和当前堆的总容量相同，说明只有2个元素了，一个是根元素，一个是根的左元素
        if (leftPos == currentSize) {
            // 这时候如果根左元素data[2]比根元素data[1]小，那么就交换二者位置
            if (data[2].getData() < data[1].getData()) {
                temp = data[2];
                data[2] = data[1];
                data[1] = temp;
            }
        }
        else {
            // 保持循环的条件是该节点的左位置小于当前堆中元素个数，那么该节点必定还有右子元素并且位置是左子元素位置+1
            while (leftPos < currentSize) {
                // 获取当前位置的左子节点的值
                leftValue = data[leftPos];
                // 获取当期那位置的右子节点的值
                rightValue = data[leftPos + 1];
                // 如果当前值既小于左子节点又小于右子节点，那么则说明当前值位置是正确的
                if (data[currentPos].getData() < leftValue.getData()
                        && data[currentPos].getData() < rightValue.getData()) {
                    break;
                }
                // 否则，比较左子节点和右子节点
                // 如果左子节点小于右子节点（当然了，同时小于当前节点），那么左子节点和当前节点互换位置
                else if (leftValue.getData() < rightValue.getData()) {
                    temp = data[currentPos];
                    data[currentPos] = leftValue;
                    data[leftPos] = temp;
                    // 同时更新当前位置是左子节点的位置,并且新的左子节点的位置为左子节点的左子节点
                    currentPos = leftPos;
                    leftPos = currentPos * 2;
                }
                // 如果右子节点小于左子节点(当然了，同时小于当前节点），那么右边子节点和当前节点互换位置
                else {
                    temp = data[currentPos];
                    data[currentPos] = rightValue;
                    data[leftPos + 1] = temp;
                    // 同时更新当前位置是右子节点的位置,并且新的左子节点的位置为右子节点的左子节点
                    currentPos = leftPos + 1;
                    leftPos = currentPos * 2;
                }
            }
        }
        return minValue;
    }
}

마지막으로 K-way 결합기를 구현해 보겠습니다. 구현하기는 매우 쉽지만 일부 첨자 연산에 있어서는 특별한 주의가 필요합니다. 보편적이기를 원하기 때문에 k와 n이 모두 전달됩니다. 실제로 k와 n을 미리 계획하면 이러한 숫자를 내부적으로 전혀 유지할 필요가 없습니다. 최소값만 저장하면 되기 때문입니다. 더미.

package com.charles.algo.kwaymerge;
import java.util.ArrayList;
import java.util.List;
/**
 *
 * 这个类用于演示K路合并
 *
 * @author charles.wang
 *
 */
public class KWayMerger {
    private KWayMerger() {
    }
    /**
     * k路合并，这里的指导思想如下：
     *
     * (1)首先构造一个最小堆，其中堆中的元素初始值为每个数组中的最小元素
     * (2)每次从最小堆中打印并且删除最小元素，然后把这个最小元素所在的数组中的下一个元素插入到最小堆中 (3)每次（2）结束后调整堆来维持这个最小堆
     */
    public static void mergeKWay(int k, int n, List<int[]> arrays) {
        // 这里存储了所有每个数组的当前的下标,在没有开始插入之前，每个数组的当前下标都设为0
        int[] indexInArrays = new int[k];
        for (int i = 0; i < k; i++) {
            indexInArrays[i] = 0;
        }
        // 首先构造一个最小堆,其大小为k
        MinHeap minHeap = new MinHeap(k);
        // 第一步，依次吧每个数组中的第一个元素都插入到最小堆
        // 然后把所有数组的下标都指向1
        for (int i = 0; i < k; i++) {
            // 这里每个都构造TrackableData对象：
            // 其中：arrays.get(i)[0]表示它值为第i个数组的下标为0的元素（也就是第i个数组的第一个元素）
            // i表示这个对象来自于第i个数组
            minHeap.insert(new TrackableData(arrays.get(i)[0], i));
            indexInArrays[i] = 1;
        }
        // 第二步，对最小堆进行反复的插入删除动作
        TrackableData currentDeletedData;
        TrackableData currentInsertedData;
        int arrayIdForDeletedData;
        int nextValueIndexInArray;
        // 循环的条件是k个数组中至少有一个还有值没有被插入到minHeap中
        while (true) {
            // 这个变量维护了有多少个数组当前下标已经越界，也就是数组所有元素已经被完全处理过
            int noOfArraysThatCompletelyHandled = 0;
            // 就是去查询维护所有数组当前下标的数组，如果都越界了，那么就说明都比较过了
            for (int i = 0; i < k; i++) {
                if (indexInArrays[i] == n)
                    noOfArraysThatCompletelyHandled++;
            }
            // 如果所有的数组中的所有的值都比较过了，那么查看堆中内容是否为空。
            if (noOfArraysThatCompletelyHandled == k) {
                while (!minHeap.isEmpty()) {
                    currentDeletedData = minHeap.deleteMin();
                    // 打印出当前的数
                    System.out.print(currentDeletedData.getData() + " ");
                }
                break;
            }
            currentDeletedData = minHeap.deleteMin();
            // 打印出当前的数
            System.out.print(currentDeletedData.getData() + " ");
            // 获取当前的被删的数来自于第几个数组
            arrayIdForDeletedData = currentDeletedData.getComeFromArray();
            // 获取那个数组的当前下标
            nextValueIndexInArray = indexInArrays[arrayIdForDeletedData];
            // 如果当前下标没有越界，说明当前数组中还有元素，则找到该数组中的下个元素
            if (nextValueIndexInArray < n) {
                // 构造新的TrackableData，并且插入到最小堆
                currentInsertedData = new TrackableData(
                        arrays.get(arrayIdForDeletedData)[nextValueIndexInArray],
                        arrayIdForDeletedData);
                minHeap.insert(currentInsertedData);
                // 同时更新维护数组当前下标的数组，让对应数组的当前下标+1
                indexInArrays[arrayIdForDeletedData]++;
            }
            // 如果当前下标已经越界，说明这个数组已经没有任何元素了，则找下一个有值的数组的最小元素
            else {
                while (true) {
                    arrayIdForDeletedData = (arrayIdForDeletedData + 1) % k;
                    // 获取那个数组的当前下标
                    nextValueIndexInArray = indexInArrays[arrayIdForDeletedData];
                    if (nextValueIndexInArray == n)
                        continue;
                    else {
                        // 构造新的TrackableData，并且插入到最小堆
                        currentInsertedData = new TrackableData(
                                arrays.get(arrayIdForDeletedData)[nextValueIndexInArray],
                                arrayIdForDeletedData);
                        minHeap.insert(currentInsertedData);
                        // 同时更新维护数组当前下标的数组，让对应数组的当前下标+1
                        indexInArrays[arrayIdForDeletedData]++;
                        break;
                    }
                }
            }
        }
    }
                          
}

실험:

마지막으로 32개의 숫자가 있고 각 방향에 8개의 숫자가 있으며 이 8개의 숫자가 이미 정렬되어 있다고 가정해 보겠습니다.

그런 다음 K-way 병합 알고리즘을 사용하여 32개 숫자를 모두 정렬합니다.

public static void main(String[] args) {
        // 我们来演示K路合并，假设我们有4组已经排序了的数组，每组有8个数，则n=8,k=4
        int[] array1 = { 4, 5, 7, 8, 66, 69, 72, 79 };
        int[] array2 = { 3, 9, 42, 52, 53, 79, 82, 87 };
        int[] array3 = { 1, 17, 21, 31, 47, 55, 67, 95 };
        int[] array4 = { 6, 28, 49, 55, 68, 75, 83, 94 };
                                                       
        System.out.println("这里演示K路合并，其中每个数组都事先被排序了，并且长度为8,我们分4路合并");
        System.out.println("数组1为：");
        for(int i=0;i<array1.length;i++)
            System.out.print(array1[i]+" ");
        System.out.println();
                                                       
        System.out.println("数组2为：");
        for(int i=0;i<array2.length;i++)
            System.out.print(array2[i]+" ");
        System.out.println();
                                                       
        System.out.println("数组3为：");
        for(int i=0;i<array3.length;i++)
            System.out.print(array3[i]+" ");
        System.out.println();
                                                       
        System.out.println("数组4为：");
        for(int i=0;i<array4.length;i++)
            System.out.print(array4[i]+" ");
        System.out.println();
        List<int[]> arrayLists = new ArrayList<int[]>(4);
        arrayLists.add(0, array1);
        arrayLists.add(1, array2);
        arrayLists.add(2, array3);
        arrayLists.add(3, array4);
        KWayMerger kWayMerger = new KWayMerger(4, 8, arrayLists);
                                                       
        System.out.println("排序后，结果为：");
        kWayMerger.mergeKWay();
        System.out.println();
    }

최종 실행 결과는 다음과 같습니다.

분명히 결과는 정확하며 우리 방법은 반복 값을 지원합니다.

위 내용은 K-way 병합 정렬(실전 전투)에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!