ヒープ、積み上げ順序及びその応用
5560 ワード
ヒープは、データを配列形式で保存する一般的なデータ構造である.
二つの山を紹介します.一つは一番大きい山で、一つは一番小さい山です.
山ほどある性質は、A[parent(i)]==A[i]です.親ノードは比子のノードが大きい必要があります.
最小ヒープの性質はA[parent(i)]<=A[i]です.親ノードは比子ノードが小さい必要があります.
次に私達は一歩ずつ見に来ます.
まず、私達はどうやってヒープの性質を維持しますか?
上のコード:
これで山の性質の維持が完了しました.次に最大の山を作ります.これに対応する最小の山は反例です.
上のコード:
上のコード:
並べ替えが完了しました.このプロセスでは並べ替えのために改造された一番多くの方法を使用しました.
このようなデータ構造を積み上げるメリットはどこにありますか?まずデータの所在性を保証して、そして重要な応用があります.その中の一つは優先列です.よくあるアプリケーションはオペレーティングシステムの作業スケジュールです.
上のコード:
二つの山を紹介します.一つは一番大きい山で、一つは一番小さい山です.
山ほどある性質は、A[parent(i)]==A[i]です.親ノードは比子のノードが大きい必要があります.
最小ヒープの性質はA[parent(i)]<=A[i]です.親ノードは比子ノードが小さい必要があります.
次に私達は一歩ずつ見に来ます.
まず、私達はどうやってヒープの性質を維持しますか?
上のコード:
/**
* :
*
* @author mazip
*
*/
public class MaxHeapify {
int largest;
public static void main(String[] args) {
MaxHeapify maxHeap = new MaxHeapify();
// 0 0 1 0
int[] m = { 0, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
int[] n = { 0, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
maxHeap.MaxHeap1(m, 2);
for (int j = 0; j < m.length; j++) {
System.out.print(m[j] + " ");
}
maxHeap.MaxHeap2(n, 2);
System.out.println();
for (int j = 0; j < n.length; j++) {
System.out.print(n[j] + " ");
}
}
/**
* method 1
*/
public void MaxHeap1(int[] i, int node) {
int left = leftNode(node);
int right = rightNode(node);
if (left < i.length && i[left] > i[node]) {
largest = left;
} else {
largest = node;
}
if (right < i.length && i[right] > i[largest]) {
largest = right;
}
if (largest != node) {
int temp = i[node];
i[node] = i[largest];
i[largest] = temp;
MaxHeap1(i, largest);
}
}
/**
*
*
* @param i
* @param node
*/
public void MaxHeapForSort(int[] i, int node,int flag) {
int left = leftNode(node);
int right = rightNode(node);
if (left < flag && i[left] > i[node]) {
largest = left;
} else {
largest = node;
}
if (right < flag && i[right] > i[largest]) {
largest = right;
}
if (largest != node) {
int temp = i[node];
i[node] = i[largest];
i[largest] = temp;
MaxHeapForSort(i, largest,flag);
}
}
/**
* method 2
*/
public void MaxHeap2(int[] i, int node) {
for (int m = node; m < i.length;) {
int left = leftNode(m);
int right = rightNode(m);
if (left < i.length && i[left] > i[m]) {
largest = left;
} else {
largest = m;
}
if (right < i.length && i[right] > i[largest]) {
largest = right;
}
if (largest != m) {
int temp = i[m];
i[m] = i[largest];
i[largest] = temp;
m = largest;
} else {
m++;
}
}
}
/**
*
* @param m
*
* @return int
*/
public int leftNode(int m) {
return 2 * m;
}
/**
*
* @param n
*
* @return int
*/
public int rightNode(int n) {
return 2 * n + 1;
}
}これで山の性質の維持が完了しました.次に最大の山を作ります.これに対応する最小の山は反例です.
上のコード:
/**
*
* @author mazip
*
*/
public class BuildMaxHeap {
public static void main(String[] args) {
BuildMaxHeap build = new BuildMaxHeap();
int [] array={0,4,1,3,2,16,9,10,14,8,7};
build.buildHeap(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
System.out.println("");
System.out.println("-----------------");
int [] array1={0,4,1,3,2,16,9,10,14,8,7};
build.buildHeap1(array1);
for (int i = 0; i < array1.length; i++) {
System.out.print(array1[i]+" ");
}
}
/**
*
* for j.length/2 ， j.length/2+1 n
* ， ，
* ， MaxHeapify
* @param j
*/
public void buildHeap(int[] j){
MaxHeapify maxHeapiey = new MaxHeapify();
for (int i = j.length/2; i > 0; i--) {
maxHeapiey.MaxHeap2(j, i);
}
}
/**
*
* @param j
*/
public void buildHeap1(int[] j){
MaxHeapify maxHeapiey = new MaxHeapify();
for (int i = j.length/2; i > 0; i--) {
maxHeapiey.MaxHeap1(j, i);
}
}
}上のコード:
public class HeapSort {
public static void main(String[] args) {
int [] array={0,4,1,3,2,16,9,10,14,8,7};
BuildMaxHeap build = new BuildMaxHeap();
build.buildHeap(array);
MaxHeapify maxHeap = new MaxHeapify();
for(int i=array.length-1;i>1;i--){
int temp = array[1];
array[1] = array[i];
array[i] = temp;
maxHeap.MaxHeapForSort(array, 1, i);
}
for(int j=0;j<array.length;j++){
System.out.print(array[j]+" ");
}
}
}
並べ替えが完了しました.このプロセスでは並べ替えのために改造された一番多くの方法を使用しました.
このようなデータ構造を積み上げるメリットはどこにありますか?まずデータの所在性を保証して、そして重要な応用があります.その中の一つは優先列です.よくあるアプリケーションはオペレーティングシステムの作業スケジュールです.
上のコード:
/**
*
*
* 1.Insert
* 2.Maximum
* 3.ExtractMax
* 4.Increasekey key
*
* @author mazip
*
*/
public class PriorityQueue {
//
public int maximum(int[] array){
//
return array[1];
}
//
public int extractMax(int[] array){
int max=array[1];
array[1]=array[array.length];
MaxHeapify maxHeap = new MaxHeapify();
maxHeap.MaxHeapForSort(array, 1, array.length-1);
return max;
}
//key
public void increaseKey(int[] array,int i,int key){
// key
// key ， key
if(key<array[i]){
System.out.println(" ");
}else{
array[i]=key;
MaxHeapify maxHeapify= new MaxHeapify();
maxHeapify.MaxHeap1(array,i);
}
}
}