アルゴリズム-ヒープ
28692 ワード
スタック
1.スタックの基本的な実現
スタックの時間的複雑度はO(Nlogn)であり,二叉スタックを用いて実現する.
最大ヒーププロパティ:ヒープ内のノード値は常に親ノードの値より大きくなく、ヒープは常に完全なツリーです.
二叉山を配列で格納し、要素を1から格納します.
1.1 Shift Up操作
上では、count++を先に挿入し、挿入した要素を一番後ろに配置し、その要素と親ノードのサイズを比較します.親ノードより大きい場合、スタックの性質を満たさず、その要素の値が親ノードの値より小さいまで交換します.
1.2 Shift Down操作
最大の要素(配列の最初の要素)を取り出し、スタックの最後の要素と最初の要素を交換し、左ノードと右ノードを比較して、大きな要素交換を選択します.そうすれば、交換された要素が最大のスタックであることを保証できます.子供のノードがそれより小さいときに停止するまで、この手順を繰り返します.
1.3 Heapify
Heapify操作:最初はすべてのリーフノードがスタックとして見られ、最初はリーフノードではない
2.その場のヒープの並べ替え
現在の最大要素を最後の要素と交換し、前からshift down操作を行い、最大要素が順に前から後ろに配列されるまで繰り返します.
3.インデックススタック
1つは、私たちのスタックの要素が文字列であれば、スタックを構築するときに要素を交換する時間がかかります.2つ目は、私たちが構築すると、スタックにインデックスを付けるのが難しいということです.
≪索引ヒープの構築｜Build Index Heap｜oem_src≫:要素ごとに1つの索引値が対応します.
スタック構築が完了すると、形成されるインデックススタックは、可視データの位置が変化せず、データが変化するインデックス値に基づいて形成されるスタックである
reverse配列を使用して逆検索:
1.スタックの基本的な実現
スタックの時間的複雑度はO(Nlogn)であり,二叉スタックを用いて実現する.
最大ヒーププロパティ:ヒープ内のノード値は常に親ノードの値より大きくなく、ヒープは常に完全なツリーです.
二叉山を配列で格納し、要素を1から格納します.
1.1 Shift Up操作
上では、count++を先に挿入し、挿入した要素を一番後ろに配置し、その要素と親ノードのサイズを比較します.親ノードより大きい場合、スタックの性質を満たさず、その要素の値が親ノードの値より小さいまで交換します.
public void insert(Item item) {
assert count + 1 <= capacity;
data[count + 1] = item;
count++;
shifUp(count);
}
private void shifUp(int k) {
while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {
swap(k, k / 2);
k /= 2;
}
}1.2 Shift Down操作
最大の要素(配列の最初の要素)を取り出し、スタックの最後の要素と最初の要素を交換し、左ノードと右ノードを比較して、大きな要素交換を選択します.そうすれば、交換された要素が最大のスタックであることを保証できます.子供のノードがそれより小さいときに停止するまで、この手順を繰り返します.
/**
*
* @return
*/
public Item extractMax() {
assert count > 0;
Item ret = data[1];
swap(1, count);
count--;
shiftDown(1);
return ret;
}
public void shiftDown(int k) {
while (2 * k <= count) {
int j = 2 * k;
//
if (j + 1 <= count && data[j + 1].compareTo(data[j]) > 0) {
j++;
}
// ，
if (data[k].compareTo(data[j]) >= 0) {
break;
}
swap(k, j);
k = j;
}
}1.3 Heapify
Heapify操作:最初はすべてのリーフノードがスタックとして見られ、最初はリーフノードではない
(count/2)から始まり、その後、そのノードからShift Down操作、すなわち最初の22からShift Down操作が開始される.このときインデックス5という位置要素もこの性質を満たす.すべてが満たされるまで、この操作を繰り返します. public Heapify(Item arr[]){
int n=arr.length;
data= (Item[]) new Comparable[n+1];
capacity=n;
// arr data
for (int i = 0; i < n; i++) {
data[i+1]=arr[i];
}
count=n;
// Shift Down
for (int i = count/2; i >= 1 ; i--) {
shiftDown(i);
}
}2.その場のヒープの並べ替え
現在の最大要素を最後の要素と交換し、前からshift down操作を行い、最大要素が順に前から後ろに配列されるまで繰り返します.
package com.liuyao.heap;
import com.liuyao.utils.SortHelper;
/**
* Created By liuyao on 2018/4/27 15:49.
*/
public class HeapSort {
private HeapSort(){}
public void sort(Comparable[] arr){
int n=arr.length;
// ， 0
// ( -1)/2
// =n-1
for (int i = (n-1-1)/2; i >=0 ; i--) {
shiftDown2(arr,n,i);
}
for (int i = n-1; i >0 ; i--) {
swap(arr,0,i);
shiftDown2(arr,i,0);
}
}
// i j
private static void swap(Object[] arr, int i, int j){
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// shiftdown ， swap ,
// 。
public void shiftDown2(Comparable[] arr,int n,int k){
// Comparable e=arr[k];
while (2*k+1int j=2*k+1;
if (j+11].compareTo(arr[j])>0){
j+=1;
}
if (arr[k].compareTo(arr[j])>0){
break;
}
swap(arr,k,j);
// arr[k]=arr[j];
k=j;
}
// arr[k]=e;
}
public static void main(String[] args) {
Integer[] a={2,3,6,8,1,4,5,7};
new HeapSort().sort(a);
SortHelper.print(a);
}
}
3.インデックススタック
1つは、私たちのスタックの要素が文字列であれば、スタックを構築するときに要素を交換する時間がかかります.2つ目は、私たちが構築すると、スタックにインデックスを付けるのが難しいということです.
≪索引ヒープの構築｜Build Index Heap｜oem_src≫:要素ごとに1つの索引値が対応します.
スタック構築が完了すると、形成されるインデックススタックは、可視データの位置が変化せず、データが変化するインデックス値に基づいて形成されるスタックである
package com.liuyao.heap;
/**
* Created By liuyao on 2018/4/18 20:38.
*/
public class IndexMaxHeap<Item extends Comparable> {
public Item[] data; //
public int[] indexes; //
public int count; //
public int capacity;
// , , capacity
public IndexMaxHeap(int capacity) {
data = (Item[]) new Comparable[capacity + 1]; // 1
indexes = new int[capacity + 1];
count = 0;
this.capacity = capacity;
}
//
public int size() {
return count;
}
// ,
public boolean isEmpty() {
return count == 0;
}
// , i, item
// i , 0
public void insert(int i, Item item) {
assert count + 1 <= capacity;
assert i + 1 >= 1 && i + 1 <= capacity;
i+=1;
data[i] = item;
indexes[count+1]=i;
count++;
shifUp(count);
}
// , data ,
private void shifUp(int k) {
while (k > 1 && data[indexes[k / 2]].compareTo(data[indexes[k]]) < 0) {
swapIndexes(k, k / 2);
k /= 2;
}
}
private void swap(int i, int j) {
Item item = data[i];
data[i] = data[j];
data[j] = item;
}
// i j
private void swapIndexes(int i, int j){
int t = indexes[i];
indexes[i] = indexes[j];
indexes[j] = t;
}
// ,
public Item getMax() {
assert count > 0;
return data[indexes[1]];
}
// ，
public int getMaxIndex(){
assert count>0;
return indexes[1]-1;
}
public Item getItem(int i){
assert i+1 >=1 && i+1 <=capacity;
return data[i+1];
}
// , ，
public Item extractMax() {
assert count > 0;
Item ret = data[indexes[1]];
swapIndexes(1, count);
count--;
shiftDown(1);
return ret;
}
// ,
public int extractMaxIndex(){
assert count>0;
int ret=indexes[1]-1;
swapIndexes(1,count);
count--;
shiftDown(1);
return ret;
}
// , data ,
public void shiftDown(int k) {
while (2 * k <= count) {
int j = 2 * k;
//
if (j + 1 <= count && data[indexes[j + 1]].compareTo(data[indexes[j]]) > 0) {
j++;
}
// ，
if (data[indexes[k]].compareTo(data[indexes[j]]) >= 0) {
break;
}
swapIndexes(k, j);
k = j;
}
}
public void change(int i,Item newItem){
i+=1;
data[i]=newItem;
// indexes[j] = i, j data[i]
// shiftUp(j), shiftDown(j)
for (int j = 1; j <=count ; j++) {
if (indexes[j]==i){
shifUp(j);
shiftDown(j);
return;
}
}
}
public static void main(String[] args) {
IndexMaxHeap maxHeap = new IndexMaxHeap<>(100);
int N = 15;
int M = 100;
for (int i = 0; i < N; i++) {
maxHeap.insert(i,new Integer((int) (Math.random() * M)));
}
Integer[] arr = new Integer[N];
for (int i = 0; i < N; i++) {
arr[i] = maxHeap.extractMax();
System.out.print(arr[i] + " ");
}
}
}
reverse配列を使用して逆検索:
package com.liuyao.heap;
/**
* Created By liuyao on 2018/4/18 20:38.
*/
public class IndexAndReverseMaxHeap<Item extends Comparable> {
public Item[] data; //
public int[] indexes; //
public int[] reverse; //
public int count; //
public int capacity;
// , , capacity
public IndexAndReverseMaxHeap(int capacity) {
data = (Item[]) new Comparable[capacity + 1]; // 1
indexes = new int[capacity + 1];
reverse=new int[capacity+1];
for (int i = 0; i <=capacity; i++) {
reverse[i]=0;
}
count = 0;
this.capacity = capacity;
}
//
public int size() {
return count;
}
// ,
public boolean isEmpty() {
return count == 0;
}
// , i, item
// i , 0
public void insert(int i, Item item) {
assert count + 1 <= capacity;
assert i + 1 >= 1 && i + 1 <= capacity;
i+=1;
data[i] = item;
indexes[count+1]=i;
reverse[i]=count+1;
count++;
shifUp(count);
}
// , data ,
private void shifUp(int k) {
while (k > 1 && data[indexes[k / 2]].compareTo(data[indexes[k]]) < 0) {
swapIndexes(k, k / 2);
k /= 2;
}
}
private void swap(int i, int j) {
Item item = data[i];
data[i] = data[j];
data[j] = item;
}
// i j
private void swapIndexes(int i, int j){
int t = indexes[i];
indexes[i] = indexes[j];
indexes[j] = t;
reverse[indexes[i]]=i;
reverse[indexes[j]]=j;
}
// ,
public Item getMax() {
assert count > 0;
return data[indexes[1]];
}
// ，
public int getMaxIndex(){
assert count>0;
return indexes[1]-1;
}
public Item getItem(int i){
assert (contain(i));
assert i+1 >=1 && i+1 <=capacity;
return data[i+1];
}
// , ，
public Item extractMax() {
assert count > 0;
Item ret = data[indexes[1]];
swapIndexes(1, count);
reverse[indexes[count]]=0;
count--;
shiftDown(1);
return ret;
}
// ,
public int extractMaxIndex(){
assert count>0;
int ret=indexes[1]-1;
swapIndexes(1,count);
reverse[indexes[count]] = 0;
count--;
shiftDown(1);
return ret;
}
// , data ,
public void shiftDown(int k) {
while (2 * k <= count) {
int j = 2 * k;
//
if (j + 1 <= count && data[indexes[j + 1]].compareTo(data[indexes[j]]) > 0) {
j++;
}
// ，
if (data[indexes[k]].compareTo(data[indexes[j]]) >= 0) {
break;
}
swapIndexes(k, j);
k = j;
}
}
public boolean contain(int i){
return reverse[i+1]!=0;
}
public void change(int i,Item newItem){
assert (contain(i));
i+=1;
data[i]=newItem;
// indexes[j] = i, j data[i]
// shiftUp(j), shiftDown(j)
// for (int j = 1; j <=count ; j++) {
// if (indexes[j]==i){
// shifUp(j);
// shiftDown(j);
// return;
// }
// }
shifUp(reverse[i]);
shiftDown(reverse[i]);
}
public static void main(String[] args) {
IndexAndReverseMaxHeap maxHeap = new IndexAndReverseMaxHeap<>(100);
int N = 15;
int M = 100;
for (int i = 0; i < N; i++) {
maxHeap.insert(i,new Integer((int) (Math.random() * M)));
}
Integer[] arr = new Integer[N];
for (int i = 0; i < N; i++) {
arr[i] = maxHeap.extractMax();
System.out.print(arr[i] + " ");
}
}
}