再学データ構造シリーズ——スタックとスタックの順序付け

1.定義
二つの条件を満たす
1.まず、完全な二叉木です(最後の層を除いて、各ノードには2人の子供がいて、最後の層には右側のいくつかのノードしか欠けていません).これを見ればわかります.http://baike.baidu.com/pic/完全二叉木/7773232/0/906289 ddefbfa 4745882 ddd 18?fr=lemma&ct=single#aid=0&pic=906289ddefbfa4745882dd18
2.最上位になるほど、ノードの重み付け値が大きくなり、その重み付け値がそれ以上になります.
サブツリーにあるすべてのノードの重み.(ここはすべてのノードですが、すべてのノードの和ではありません)
2.分類
ルートノードの重み値がツリーのノードの重み値以上のスタックを「」と呼びます.
大根の山
ルートノードの重み値がツリー内のノードの重み値以下のスタックを「」と呼びます.
小根の山
3.貯蔵
配列で保存すればいいです.もちろん私たちのコンピュータには0から作られています.

4.実現

#include <iostream>

using namespace std;

class Heap{
private:
	int *data, size;
public:
	//length_input:      
	Heap(int length_input){
		data = new int[length_input];
		size = 0;
	}
	~Heap(){
		delete[] data;
	}
	//  
	void push(int value){
		//                 ，     size       ，            
		data[size] = value;
		// current         
		int current = size;
		//         
		int	father = (current-1)/2;
		//          ，   ，         
		while (data[current] > data[father]) {
			//   
			swap(data[current], data[father]);
			//       ，        
			current = father;
			//             
			father = (current-1)/2;
		}
		//   ，    +1
		size++;
	}
	//    
	void output(){
		//         
		for (int i = 0; i < size; i++) {
			cout<<data[i]<<" ";
		}
		cout<<endl;
	}
	//      
	int top(){
		return data[0];
	}
	//       
	//pos:        
	//n:         
	void update(int pos, int n){
		//           ，    pos                
		int lchild = 2 * pos + 1, rchild = 2 * pos + 2;
		//              pos
		int max_value = pos;
		//           ，      max_value    ，     max_value
		if (lchild < n && data[lchild] > data[max_value]) {
			max_value = lchild;
		}
		if (rchild < n && data[rchild] > data[max_value]) {
			max_value = rchild;
		}
		//       if，max_value             ，
		//     pos，        ，  pos            
		if (max_value != pos) {
			//     max_value          ，      ，      
			swap(data[pos], data[max_value]);
			//        ，     
			update(max_value, n);
		}
	}
	//      
	void pop(){
		//                 
		swap(data[0], data[size-1]);
		//     1，             
		size--;
		//         0，        ，size     
		update(0, size);
	}
	//   
	// ：           
	void heap_sort(){
		//         ，       ，        
		for (int i = size -1; i >= 1; i--) {
			//       ，           data[size-1]      ，      
			swap(data[i], data[0]);
			//        ，   i+1           ，       i 
			//       i           ， data[0]
			update(0, i);
		}
	}
};

int main(){
	int arr[10] = { 12, 9, 30, 24, 30, 4, 55, 64, 22, 37 };
	Heap heap(100);
	for (int i = 0; i < 10; i++) {
		heap.push(arr[i]);
	}
	//  
	heap.output();
	cout<<heap.top()<<endl;
	heap.pop();
	heap.output();
	//   
	heap.heap_sort();
	heap.output();
	return 0;
}

5.運転結果