왜 정렬되지 않은 목록에 삽입하는 것보다 힙에 삽입하는 것이 빠릅니까?

Question

내 힙 및 정렬되지 않은 목록에 100000000 개의 요소를 삽입 한 후 힙 삽입이 실제로 더 빠릅니다 (12 초 대 20 초). 왜 이런거야? 정렬되지 않은 목록 삽입은 O(1) 인 반면 힙 삽입은 O(logn)이라고 생각합니다. 나는 또한 힙 삽입 구현이 실제로 입력의 수에 비례하지 않는다는 것을 알았다. 이것은 또한 나를 혼란스럽게합니다. 여기

내가 실행 한 코드입니다 : 이것은 삽입의 힙 구현이

int main() 
{ 
    clock_t unsortedStart; 
    clock_t heapStart; 

    double unsortedDuration; 
    double heapDuration; 

    int num_pushes = 100000000; 
    int interval = 10000; 

    ofstream unsorted ("unsorted.txt"); 
    ofstream heap ("heap.txt"); 

    UnsortedPQ<int> unsortedPQ; 
    HeapPQ<int> heapPQ; 

    unsortedStart = clock(); 

    for (int i = 0; i < num_pushes; ++i) 
    { 
     if (i % interval == 0) { 
      unsortedDuration = (clock() - unsortedStart)/(double) CLOCKS_PER_SEC; 
      unsorted << unsortedDuration << " " << i << endl; 
     } 

     unsortedPQ.insertItem(rand() % 100); 
    } 

    heapStart = clock(); 
    for (int i = 0; i < num_pushes; ++i) 
    { 
     if (i % interval == 0) { 
      heapDuration = (clock() - heapStart)/(double) CLOCKS_PER_SEC; 
      heap << heapDuration << " " << i << endl; 
     } 
     heapPQ.insertItem(rand() % 100); 
    } 
    return 0; 
} 

(std::vector 사용) :

이

template <class T> 
void HeapPQ<T>::insertItem(T data) { 
    //insert into back of heap (std::vector) 
    dataArray.push_back(data); 
    int i = dataArray.size() - 1; 

    //sifts the inserted element up 
    while (i != 0 && dataArray[(i - 1)/2] > dataArray[i]) { 
     swap(dataArray[i], dataArray[(i - 1)/2]); 
     i = (i - 1)/2; 
    } 
} 

이 삽입물의 정렬되지 않은리스트의 구현이 (std::list 사용)입니다 :

//pushes element to the back of a std::list 
template <class T> 
void UnsortedPQ<T>::insertItem(T data) { dataList.push_back(data); } 

Answer 1

힙에 삽입하는 것이 O(logn)은 모든 삽입이 최대 O(logn) 단계를 취할 수 있음을 의미합니다. 그것은 그것이해야한다는 것을 의미하지는 않습니다.

예를 들어 요소를 삽입하는 평균 비용은 O(1)입니다. 왜? (- 계산이 더 복잡하지만, 동작은 동일하게 유지 0..99 (rand() % 100)가 삽입 된 숫자 만 현재 버전에서)

단순 들어, 당신이 임의의 순서 만 0 a와 1의 삽입 가정하자. 2*n 요소가 삽입 된 후, 약 n0들과 힙 n1의가있을 것이고, 같이 보일 것이다 힙은 다음과 같습니다

        0 
           0 0 
           00 00 
          ............... 
         0 0 0 0 0 0 0 
         11 11 11 11 11 11 11 

그래서 기본적으로 1의 마지막 수준에서 모두는 k 및 0 레벨은 0..k-1입니다.

1. 1이 삽입 된 경우 아무 작업도 수행하지 않습니다 (위의 2).
2. 0이 삽입 된 경우 최대 하나의 스왑이 있습니다 (1는 마지막 레벨보다 위에 있지만 2 레벨 이상일 수 있음).

평균적으로 측정 값은 0.5이며, k이 아닙니다.

동일한 점근 시간을 사용하면 벡터 및 목록에 삽입하는 데 드는 비용이 모두 (상환 된) 비용까지 줄어 듭니다. 목록은 느린 것 같습니다 (내 가정은 삽입 할 때마다 new을 통해 힙에 요소를 할당해야하는데 이것은 매우 느린 작업입니다. 비용은 삽입 된 개체의 크기, 따라서 어느 것이 더 빠르는지를 변화시킬 수있다).

---

은의이 번호가 균일 한 dstribution [0..99]에 의해 생성되는 사용자의 경우, 좀 더 자세히 살펴 보자. n>>100 삽입 후 우리는 다음과 같은 상황이있을 것이다 (이 일부 손을 흔들며 참여하지만, 요점이 명확해야한다) :

힙의 마지막 레벨 ( k 번째는) n/2 요소를 가지고와 숫자로 구성

1. 50..99. 따라서 가능한 숫자의 50 % (예 : 50..99)는 전환 할 필요가 없습니다.
2. 힙의 두 번째 마지막 레벨 (k-1 번째)은 n/4 개의 요소를 가지며 숫자는 25..49입니다. 이는 정확히 1 교대가 필요한 숫자의 25 %를 의미합니다.
3. 레벨 k-2은 n/8 개의 요소를 가지며 숫자는 13..24입니다.
4. 위의 레벨은 log 100/log 2입니다. 내부는 0입니다. 가능한 최대 이동 수는 m=log 100/log 2이며 힙의 요소 수인 n과는 별개입니다.

그래서 삽입에 대한 최악의 경우 비용이 log 100/log 2 것 평균 비용이 더 작은 있습니다

E(insertion)=0*1/2+1*1/4+2*1/8+...<=1.0 

즉 평균적으로 우리가 삽입 미만 1 변화가있다.

NB :이 힙에 삽입하는 O(1)의 비용을 상각 한 것을 의미하지 않는다 - 당신이 임의의 순서에없는 숫자를 삽입 만하면 것인지 먼저 99의 다음 98들, ..., 다음 0의 삽입 당 비용은 O(log n)입니다.