더미 의 응용 (우선 순위 대기 열, 대량의 데이터 처리, 더미 정렬)

1. 우선 순위 대기 열
1. 기본 적 인 사고
사실 대기 열 을 사용 하여 이 루어 질 수 있 지만 피 할 수 없 는 것 은 Push () 와 Pop () 작업 입 니 다. 적어도 한 개의 시간 복잡 도 는 O (N) 이 고 다른 한 개의 시간 복잡 도 는 O (1) 입 니 다. 사용 할 수 있 는 쌍 을 사용 하면 삽입 할 수 있 는 시간 복잡 도 는 O (lgN) 이 며 삭제 할 때 시간 복잡 도 는 O (1) 입 니 다.
2. 구체 적 실현
어댑터 모드 를 통 해 이 루어 집 니 다. 힙 에 대한 패 키 징 을 통 해 이 루어 집 니 다.
(1) 더미 의 실현
구체 적 으로 실현 하기 전에 이미 블 로그 에서 설명 한 적 이 있 는데, 여 기 는 구체 적 으로 설명 하지 않 겠 습 니 다.
(2) 우선 순위 대기 열의 실현

template class Compare=Less>
class PriorityQueue
{
public:
	void Push(const T& x)
	{
		_hp.Push(x);
	}

	void Pop()
	{
		_hp.Pop();
	}
	
	T& Top()
	{
		return Top();
	}

	size_t Size()
	{
		return _hp.Size();
	}

	bool Empty()
	{
		return _hp.Empty();
	}

protected:
	Heap _hp;
};

2. 100 w 개수 중 가장 큰 앞 K 개 수 를 찾 아 라.
1. 기본 적 인 사고
(1) 방법 1: 100 크기 의 배열 을 만 들 고 연료 가 한 쪽 에 있 는 100 w 의 수 를 만 듭 니 다.
(2) 방법 2: 이 100 w 개 수 를 메모리 에 넣 고 정렬 하여 100 개 수 를 찾 습 니 다.
(3) 방법 3: 앞의 두 가 지 는 시간 복잡 도가 너무 높 고 효율 이 너무 낮 기 때문에 상기 두 가지 방법 을 사용 하지 않 고 쌓 아서 실현 한다.
2. 구체 적 인 사고
도대체 큰 뿌리 더미 로 이 루어 질 까, 작은 뿌리 더미 로 이 루어 질 까?
큰 뿌리 더미 와 작은 뿌리 더 미 는 첫 번 째 수가 가장 작 거나 가장 작 음 을 보장 할 수 있다.큰 뿌리 더 미 를 선택 하면 이 100 개 중에서 첫 번 째 숫자 가 가장 크다 는 것 을 보증 할 수 밖 에 없다. 왜냐하면 두 번 째 큰 숫자 는 들 어 오지 못 할 수도 있 기 때문이다. (그러면 왜 가장 작은 잎 노드 와 비교 하지 않 습 니까? 가장 작은 잎 노드 는 이미 선택 한 100 개 중 가장 작은 것 이 라 고 보장 할 수 없 기 때 문 입 니 다)
그래서 작은 뿌리 더 미 를 선택 하면 선택 한 100 개 보다 가장 작은 큰 숫자 가 더미 에 들 어가 고 내 려 가면 뿌리 노드 의 값 이 가장 작은 것 을 보증 할 수 있다.
3. 대량의 데이터 처리
1. 제목
2015 년 설 연 휴 에는 A 사의 결제 앱 인 모 바 오 와 T 사 모 편지 봉투 가 난투 극 을 벌 였 다.설 이후 피크 이후 회사 리 더 는 백 스테이지 의 공 성 사자 에 게 백 스테이지 의 대량의 데 이 터 를 분석 하 라 고 요구 했다.지역 별 보너스 금액 이 가장 많은 상위 100 명의 사용 자 를 분석 해 달라 고 먼저 요청 했다.현재 가장 많은 인원 을 알 고 있 는 s 지역 에는 약 1000 w 의 사용자 가 있다.알고리즘 을 써 서 실현 하도록 요구 하 다.
2. 기본 적 인 사고
사실은 응용 2 의 기본 적 인 사고 와 같다.배열 아래 표 시 된 1 에서 100 사이 의 요 소 를 한 더미 로 만 든 다음 에 뒤의 요 소 는 뿌리 노드 와 계속 비교 하여 쌓 을 지 안 들 어 갈 지 결정 한다.
3. 구체 적 실현
코드 는 다음 과 같 습 니 다:

void AdjustDown(int* pKArray, size_t root, size_t size)
{
	size_t parent = root;
	size_t child = root * 2 - 1;
	while (child < size)
	{
		if (child + 1 < size&&pKArray[child + 1] < pKArray[child])
		{
			++child;
		}
		if (pKArray[parent] > pKArray[child])
		{
			std::swap(pKArray[parent], pKArray[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}



void GetTopK(const vector& moneys, int n, int k)
{
	assert(n > k);
	int* topKArray = new int[k];
	for (size_t i = 0; i < k; ++i)
	{
		topKArray[i] = moneys[i];
	}
	//    
	for (int i = (k - 2) / 2; i >= 0; --i)
	{
		AdjustDown(topKArray, 0, k);
	}
	for (size_t i = 0; i < k; ++i)
	{
		cout << topKArray[i] << " ";
	}
	cout << endl;
	delete[] topKArray;
}




void GreatRedPacket(vector& moneys)
{
	srand(time(0));
	moneys.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		moneys.push_back(rand() % 1000);
	}

	for (int j = N - K; j < N; ++j)
	{
		moneys[j] = rand()%N;
	}

}

테스트 용례:

void Test()
{
	vector arr;
	GreatRedPacket(arr);
	GetTopK(arr,N,K);
	cout << endl;
}

3. 더미 정렬
1. 기본 적 인 사고방식:
쌓 기 정렬 은 사실 정렬 을 선택 하 는 것 이다. 단지 매번 다시 쌓 아야 할 뿐이다.
2. 단체 사고
승 서 를 예 로 들 면:
그럼 큰 무 더 기 를 만 드 는 건 가요? 작은 무 더 기 를 만 드 는 건 가요?
(1) 작은 무 더 기 를 만 들 면 가장 작은 요 소 를 표시 하 는 것 이 가장 작은 것 이지 만 가장 작은 것 을 선택 할 때마다 나머지 는 새로 작은 더미 로 조정 해 야 한다.
(2) 무 더 기 를 쌓 으 면 뿌리 노드 가 가장 큰 값 입 니 다. 매번 마지막 잎 노드 의 값 과 교환 한 다음 에 교환 한 뿌리 노드 를 아래로 조정 하면 새로 쌓 지 않 아 도 됩 니 다.
3. 구체 적 실현
상승 순 서 를 실현 하 다.
코드 는 다음 과 같 습 니 다:

void AdjustDown(int* a, size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size&&a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child]>a[parent])
		{
			std::swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, size_t size)
{
	//  
	for (int i = (size-2) / 2; i >= 0; --i)
	{
		AdjustDown(a, size, i);
	}
	for (size_t i = 0; i < size; ++i)
	{
		std::swap(a[0], a[size - i - 1]);//        
		AdjustDown(a, size - i - 1, 0);//  
	}
}

테스트 용례:

void Test()
{
	int a[] = { 10, 11, 12, 14, 12, 1, 2, 3, 4, 15, 19 };
	int len = sizeof(a) / sizeof(a[0]);
	HeapSort(a, len);
	for (size_t i = 0; i < len; ++i)
	{
		cout << a[i] << " ";
	}
}