データ構造学習——ヒープ

1基本的な紹介
ヒープデータ構造は、完全な二叉ツリーと見なされる配列オブジェクトです.ヒープのアクセスは三つの関数で行うことができます.

parent(i)
    return floor(i/2);
left(i)
    return 2i;
right(i)
    return 2i + 1;

left操作は1ステップ左シフト操作で完了できます.right操作は左シフトとステータス+1で実現できます.parent操作はiを右にシフトして得られます.実装では通常、マクロまたはインライン関数を使用して、これらの3つの動作を実現します.
二叉の山は二種類あります.一番大きい山と一番小さい山です.山のようにある

A[i] >= A[left(i)] && A[i] >= A[right(i)]

一番小さいのは

A[i] <= A[left(i)] && A[i]<= A[right(i)]

一番山の並べ替えアルゴリズムでは、一番大きな山を使って、一番小さい山は普通優先列を作る時に使います.山は木のように見えることができます.結点の山の中の高さは本結点から葉までの一番長い簡単な下がり方の上の数と定義されています.山の高さを木の根の高さとして定義します.
2原理部分
いくつかの基本関数について説明します.
maxHeappify()、運転時間はO(lgn)で、ヒープの性質を維持するために使用されます.
bulidMaxHeap()は、線形時間で動作し、無秩序な入力配列に基づいて最大の山を構築することができます.
heappSort()は、運転時間はO(nlgn)であり、配列の元の場所を並べ替えます.
2.1ヒープの性質を維持する
入力は1つの配列Aと下付きiであり、maxHeappifyが呼び出された時、我々はleftIiとright(i)を根とする2本の二叉樹が最大山であると仮定していますが、この時A[i]は子供より小さいかもしれません.maxHeappifyはA[i]を一番多くの山に「下降」させ、iを根とする子樹を最大の山にする.疑似コードは以下の通りです.

maxHeapify(A,i)
    l <- left(i)
    r <- right(i)
    if l <= heap-size[A] and A[l] > A[i]
        then largest <- l
        else largest <- i
    if r <= heap-size[A] and A[r] > A[largest]
        then largest <- r
    if largest != i
        then exchange A[i] <-> A[largest]  //   i          
            maxHeapify(A,largest);         //     

2.2ビルド
一つの配列A［1…n］(ここでn＝length［A］)を底から上に向かって最大の山にすることができます.サブアレイA［flor(n/2)+1).n］の要素はすべてツリーの中の葉っぱノードであるので、それぞれ一つの要素だけを含む山として見られます.buildMAXHeapは、ツリー内の他のノードごとにmaxHeaphiyを呼び出します.疑似コードは以下の通りです.

buildMaxHeap(A)
    heap-size[A] <- length[A]
    for i <- floor(length[A] / 2) downto 1
        do max-heapify(A,i)

2.3積み上げ順序付けアルゴリズム
最初に、スタック並び替えアルゴリズムはまず、入力配列A［1.n］(ここn=length[A])をbuildMaxHeapで一番大きな山に構成しています.配列の中の最大要素はルートA［1］にあるので、それをA[n]と交換することで最終的に正しい位置に達することができます.現在、ヒープからノードnを取り除くと(heap-size[A]を減らすことによって)、A[1.n-1]を最大の山に簡単に作ることができます.元の根の子は最大の山です.新しい根の要素は最大の山の性質に反するかもしれません.これは、maxHeapplity(A,1)を呼び出してその性質を維持することができ、A［1.(n−1)］で最大の山を作ります.積み上げアルゴリズムはこのプロセスを繰り返し、積み上げの大きさはn-1から2まで下がる.

heapSort(A)
    buildMaxHeap(A)
    for i <- length[A] downto 2
        do exchange A[1] <-> A[i]
            heap-size[A] <- heap-size[A] - 1
            maxHeapify(A,1)

積み上げ順序付けアルゴリズムは非常にナイスなアルゴリズムであるが、実際の応用においては、高速秩序化のための良い実現は、しばしばスタック順序より優れている.
3 java実現
3.1データ構造
Heap.java

import java.io.Serializable;

/**
 * Date: 2014/8/17
 * Time: 16:02
 */
public class Heap implements Serializable{
    private int heapLength;
    private int [] data;

    public int getHeapLength() {
        return heapLength;
    }

    public void setHeapLength(int heapLength) {
        this.heapLength = heapLength;
    }

    public int[] getData() {
        return data;
    }

    public void setData(int[] data) {
        this.data = data;
    }
}

3.2操作類
HeappSort.java

/**
 * Created with IntelliJ IDEA.
 * Date: 2014/8/17
 * Time: 15:39
 */
public class HeapSort {
    public final static int getLeft(int i) {
        return i << 1;
    }

    public final static int getRight(int i) {
        return (i << 1) + 1;
    }

    public final static int getParent(int i) {
        return i >> 1;
    }

    /**
     *       
     *
     * @param heap
     * @param i
     */
    public static void maxHeapify(Heap heap, int i) {
        if (null == heap || null == heap.getData() || heap.getData().length <= 0 || i < 0)
            return;
        int l = getLeft(i);
        int r = getRight(i);
        int largest = 0;
        if (l < heap.getHeapLength() && heap.getData()[l] > heap.getData()[i])
            largest = l;
        else
            largest = i;
        if (r < heap.getHeapLength() && heap.getData()[r] > heap.getData()[largest])
            largest = r;
        if (largest != i) {
            int tmp = heap.getData()[i];
            heap.getData()[i] = heap.getData()[largest];
            heap.getData()[largest] = tmp;
            maxHeapify(heap, largest);
        }
    }

    /**
     *      
     *
     * @param array
     * @return
     */
    public static Heap bulidMaxHeap(int[] array) {
        if (null == array || array.length <= 0)
            return null;
        Heap heap = new Heap();
        heap.setData(array);
        heap.setHeapLength(array.length);
        for (int i = (array.length >> 1); i >= 0; i--)
            maxHeapify(heap, i);
        return heap;
    }

    /**
     *    
     *
     * @param array
     */
    public static void heapSort(int[] array) {
        if (null == array || array.length <= 0)
            return;
        Heap heap = bulidMaxHeap(array);
        if (null == heap)
            return;
        for (int i = heap.getHeapLength() - 1; i > 0; i--) {
            int tmp = heap.getData()[0];
            heap.getData()[0] = heap.getData()[i];
            heap.getData()[i] = tmp;
            heap.setHeapLength(heap.getHeapLength() - 1);
            maxHeapify(heap, 0);
        }
    }
}

3.3試験類
Main.java

public class Main {

    public static void main(String[] args) {
        int a[] = {9, 3, 4, 1, 5, 10, 7};
        System.out.println("Hello World!");
        Sort sort = new Sort();
//        sort.bubbleSort(a);
//        sort.selectSort(a);
//        sort.insertionSort(a);
        HeapSort.heapSort(a);
        for (int i = 0; i < a.length; i++)
            System.out.println(a[i]);
    }
}

補足ノート
Top k問題はヒープを使って解決できます.
例えば、長さNの配列Aから前のk個の大きさのk個の数(k＜N)を探すと、ブロックの長さがkの最小の山を維持し、まずAの前のk個の要素を使用して、この最小の山を初期化し、K＋1〜Nを遍歴し続け、もしある要素が最小の山の根より大きいならば、それを積み重ねさせ、最後に遍歴した後、前のk個のデータを見つけることができる.
このようにすると総時間O(k＊logk+(n-k)＊logk)=O(n＊logk)となります.