第10章の演習

ソースのダウンロード

今後の演習では，ホームフォルダの下にmis2というフォルダを作って， そこで作業することを前提とする．作成していない時は，ターミナルから 
mkdir ~/mis2
を実行する． http://opendatastructures.orgのc++ edition, c++ sources ( C++ sources(講義独自版) ) からダウンロードしたファイルをホームフォルダの下のmis2に置く．ods.cpp.tgzというファイルができた時は， 
cd ~/mis2
tar zxvf ods-cpp.tgz
ods-cpp.tarというファイルができた時は， 
cd ~/mis2
tar xvf ods-cpp.tar
を実行するとcppというフォルダができる．Finderからダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．

[投票]ヒープを使ったことがある?

  1. Priority Queue(優先度付きキュー) を使ったことがある
  2. ヒープソートのプログラムを書いたことがある．
  3. 1，2の両方が当てはまる．
  4. 1，2の両方共当てはまらない．

演習(BinaryHeap)

~/mis2/cpp 以下にbinaryHeapTest.cpp というファイルを作成する． 
#include "BinaryHeap.h"
#include <iostream>
#include <vector>
#include <algorithm>

int main(){
  ods::BinaryHeap<int> pq;
  std::vector<int> vs;
  for(int i = 2; i < 50; i++){
    vs.push_back(i);
  }
  std::random_shuffle(vs.begin(),vs.end());
  for(size_t k = 0; k < vs.size(); k++) pq.add(vs[k]);
  while (pq.size() > 0)
    std::cout << pq.remove() << " ";
  std::cout << std::endl;
}
これを， 
cd ~/mis2/cpp
g++-5 -Wall  -o binaryHeapTest binaryHeapTest.cpp
でコンパイルし， 
./binaryHeapTest
で実行する．

演習(MeldableHeap)

~/mis2/cpp 以下にmeldableHeapTest.cpp というファイルを作成する． 
#include "MeldableHeap.h"
#include <iostream>
#include <vector>
#include <algorithm>

int main(){
  ods::MeldableHeap1<int> pq;
  std::vector<int> vs;
  for(int i = 2; i < 50; i++){
    vs.push_back(i);
  }
  std::random_shuffle(vs.begin(),vs.end());
  for(size_t k = 0; k < vs.size(); k++) pq.add(vs[k]);
  while (pq.size() > 0)
    std::cout << pq.remove() << " ";
  std::cout << std::endl;
}
これを， 
cd ~/mis2/cpp
g++-5 -Wall  -o meldableHeapTest meldableHeapTest.cpp
でコンパイルし， 
./meldableHeapTest
で実行する．