国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

小根堆實現

silencezwm / 2882人閱讀

摘要:如果有一個關鍵字的集合把所有元素按完全二叉樹的順序存儲方式存放在一個一維數組中,并且滿足且向上取整則稱這個集合為小根堆。

如果有一個關鍵字的集合K={k0,k1,k2, ..., kn-1}, 把所有元素按完全二叉樹的順序存儲
方式存放在一個一維數組中,并且滿足
ki <= k2i+1 且 ki <= k2i+2 (i = 0, 1, ..., (n-2)/2 向上取整)
則稱這個集合為小根堆。

創建

復制堆數組

找到最初的調整位置,即最后一個分支結點

自底向上逐步擴大形成堆

向前換一個分支結點

插入

將待插入元素插入已建成堆的最后面

沿著出入位置所在的分支逐步向上調整

刪除

將頂元素刪除

將數組中最后一個元素放到堆頂

自頂向下調整

代碼實現

import java.util.Arrays;

/**
 * Created by mico on 2017/2/5.
 */
public class HeapExam {
    /**
     * 小根堆初始化
     *
     * @param a
     * @param length
     */
    public void minHeap(int a[], int length) {
        for (int i = length >> 1; i >= 0; i--) {
            adjustMinHeap(a, length, i);
        }
    }

    /**
     * 排序 topn
     *
     * @param a
     * @param length
     */
    public void sort(int a[], int length) {
        for (int i = 0, last = length; i < length - 1; i++) {
            swap(a, 0, --last);
            minHeap(a, last);

        }
    }


    /**
     * 小根堆調整
     *
     * @param a
     * @param length
     * @param i
     */
    private void adjustMinHeap(int[] a, int length, int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int minIndex = i;
        if (left < length && a[left] < a[i]) {
            minIndex = left;
        }
        if (right < length && a[right] < a[minIndex]) {
            minIndex = right;
        }
        if (minIndex != i) {
            swap(a, i, minIndex);
            adjustMinHeap(a, length, minIndex);
        }

    }


    /**
     * 交換 數組值
     *
     * @param a
     * @param i
     * @param j
     */
    private void swap(int[] a, int i, int j) {
        a[i] = a[i] + a[j];
        a[j] = a[i] - a[j];
        a[i] = a[i] - a[j];
    }


}

測試

public static void main(String[] args) {
        int[] a = {153, 173, 728, 9, 425, 165, 7, 233};
        //int[] arry_int={13, 38, 27, 55, 76, 65, 49, 97};
        HeapExam exam = new HeapExam();
        exam.minHeap(a, a.length);
        System.out.println("小根堆:" + Arrays.toString(a));
        exam.sort(a, a.length);
        System.out.println("排序結果:" + Arrays.toString(a));
    }

輸出

小根堆:[7, 9, 153, 173, 425, 165, 728, 233]
排序結果:[728, 425, 233, 173, 165, 153, 9, 7]

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66578.html

相關文章

  • 七大排序算法總結(java)

    摘要:前面介紹了七大算法的思想與實現步驟,下面來做一個歸總。直到無序區中的數為零,結束排序。步驟以從小到大為例,排序數組大小為。比較完以后則排序結束。堆排序思想堆排序是采用樹的形式的數據結構來進行排序的,其中每一個堆都是完全二叉樹。 前面介紹了七大算法的思想與實現步驟,下面來做一個歸總。 排序方法 平均復雜度 最壞復雜度 最好復雜度 輔助空間 穩定性 直接選擇排序 O(n^2...

    cartoon 評論0 收藏0
  • 排序算法

    摘要:排序代碼實現和一概念排序算法的穩定性穩定性穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。交換的結果導致結點的值變化了,重復,,的操作,直到沒有孩子時跳出代碼實現構建初始堆堆排序算法思想大頂堆舉例將待排序的序列構造成一個大頂堆。 排序 代碼實現:Java 和 Python 一、概念 1.1 排序算法的穩定性 穩定性:穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。也就是如果一個排序...

    kevin 評論0 收藏0
  • 排序算法

    摘要:排序代碼實現和一概念排序算法的穩定性穩定性穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。交換的結果導致結點的值變化了,重復,,的操作,直到沒有孩子時跳出代碼實現構建初始堆堆排序算法思想大頂堆舉例將待排序的序列構造成一個大頂堆。 排序 代碼實現:Java 和 Python 一、概念 1.1 排序算法的穩定性 穩定性:穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。也就是如果一個排序...

    binaryTree 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<