큐

이 기사는 대부분 또는 전체적으로 단일 출처에 의존하고 있습니다. 관련 토론은 토크 페이지에서 확인할 수 있습니다. 추가 출처에 인용문을 도입하여 이 기사의 개선에 도움을 주시기 바랍니다.출처 : 'Queap' – 뉴스 · 신문 · 서적 · 학자 · JSTOR (2013년 4월)

k = 6 및 n = 9인 Queap Q

컴퓨터 과학에서 큐는 priority 큐 데이터 구조입니다.데이터 구조에서는 임의 요소의 삽입 및 삭제와 가장 우선순위가 높은 요소의 검색이 가능합니다.각 삭제는 제거된 항목보다 구조 내에 더 오랜 시간 동안 있었던 항목 수에 대해 상각된 시간을 로그로 취합니다.삽입에는 상각된 시간이 일정하게 소요됩니다.

데이터 구조는 이중으로 연결된 목록과 2-4개의 트리 데이터 구조로 구성되며 각각 최소 우선순위 요소를 추적하도록 수정됩니다.구조체의 기본 작동은 삭제 시 목록 항목 중 하나가 삭제될 때까지 새로 삽입된 요소를 이중 링크 목록에 유지하는 것입니다. 이 목록에서 항목이 모두 2-4 트리로 이동됩니다.2-4 트리는 기존의 우선순위 정렬 순서가 아닌 삽입 순서로 요소를 저장합니다.

데이터 구조와 이름은 모두 John Iacono와 Stefan Langerman에 ^[1]의해 고안되었습니다.

묘사

queap은 O(1)의 상각시간에 요소를 삽입하는 priority 큐로 추출되는 요소보다 더 오랜 시간 히프에 k개의 항목이 있을 경우 O(log(k+2)의 최소 요소를 삭제합니다.큐잉에는 큐잉 속성이라고 불리는 속성이 있습니다.요소의 x 검색 시간은 O(lg q(x)입니다.여기서 q(x)는 n - 1 - w(x)이고 w(x)는 검색, 삽입 또는 삭제 등의 조작에 의해 액세스된 고유 항목의 수입니다.q(x)는 x의 마지막 액세스 이후 액세스되지 않은 요소의 수로 정의됩니다.실제로 큐잉 속성은 스플레이 트리 작업 집합 속성을 보완하는 것입니다. 요소 x를 검색하는 시간은 O(lg w(x))입니다.

큐는 2개의 데이터 구조(이중 링크 리스트와 2-4 트리의 수정 버전)로 나타낼 수 있습니다.이중 링크 리스트 L은 삽입 및 locate-min 조작에 사용됩니다.queap은 목록에 저장된 최소 요소에 대한 포인터를 유지합니다.리스트 l에 요소 x를 추가하기 위해 요소 x를 리스트 끝에 추가하고 요소 x의 비트 변수를 1로 설정합니다.이 작업은 요소가 목록에 있는지 또는 2-4 트리에 있는지 확인하기 위해 수행됩니다.

2-4 트리는 삭제 조작이 발생했을 때 사용됩니다.항목 x가 이미 트리 T에 있는 경우 2-4 트리 삭제 작업을 사용하여 항목을 제거합니다.그렇지 않으면 항목 x가 목록 L에 있습니다(비트 변수가 설정되어 있는지 확인).목록 L에 저장된 모든 요소가 2-4 트리에 추가되고 각 요소의 비트 변수가 0으로 설정됩니다.그런 다음 T에서 x가 삭제됩니다.

queap은 검색 트리가 아닌 2-4개의 트리 구조 속성만 사용합니다.수정된 2-4 트리 구조는 다음과 같습니다.목록 L에 x${\displaystyle {}_{}{1\mathrm{}}_{}}$, ${\displaystyle {}_{}{}_{}}$2, ${\displaystyle {x\mathrm{}}_{}}$ 3,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ {\$display style x_{1}, x_{2}, x_${3$},\dots,$x_${k$의 요소 세트가 있다고 가정합니다.삭제 조작이 호출되면 L에 저장되어 있는 요소 세트는 무한 리프를 포함한 2-4 트리의 리프에 순서대로 추가됩니다.T의 각 내부 노드에는 ${\displaystyle {포인터h}_{}}$ v$$v \ $displaystyle$ h$_$$${ $v$$$} 이$$ 있습니다$.$에서 x 0으로 가는 경로P의 각 내부 노드에는 포인터 ${\displaystyle c_{}}$ v$$\ $display c$_ {$$$v$} 이 $있습니다{\displaystyle }$.$이것$은${\displaystyle }$T - ${\displaystyle T_{}}$V${\displaystyle }$- { ${\displaystyle r}$ $}$ - { r } $display$ -$T$ _ { { t } 의 가장 작은 키를 가리킵니다.$r$ 패스 P의 각 내부 노드의 ${\displaystyle h_{}}$ v$${\$displaystyle h_{v}$ 포인터는$$ $무시$됩니다.${\displaystyle {큐}_{}}$에는 c x $(\$에 대한 포인터가 있습니다.이것은 T에서 가장 작은 요소를 가리킵니다.

큐의 적용은 처리를 위한 고우선순위 이벤트와 최고우선순위 이벤트 추출의 고유 세트를 포함한다.

운용

minL을 이중 링크 리스트 L의 최소 요소를 가리키는 포인터, ${\displaystyle {c{}_{}}_{}}$ ${\displaystyle {{x\mathrm{}}_{}}_{}}$ 0$(\$을 2-4 트리에 저장되는 최소 요소, T, k를 T에 저장되는 요소, n을 queap Q에 저장되는 요소의 총 개수라고 합니다.조작은 다음과 같습니다.

New(Q): 새로운 빈 큐를 초기화합니다.

빈 이중 링크 리스트 L과 2-4 트리 T를 초기화합니다.k와 n을 0으로 설정합니다.

Insert(Q, x): Queap에 요소 x를 추가합니다.

x 요소를 목록 L에 삽입합니다.요소 x의 비트를 1로 설정하여 요소가 목록 L에 있음을 나타냅니다.x가 목록에서 가장 작은 요소인 경우 minL 포인터를 업데이트합니다.n을 1씩 늘립니다.

최소값(Q): Queap Q에서 가장 작은 요소에 대한 포인터를 가져옵니다.

키(minL) < 키( ${\displaystyle {c{}_{}}_{}}$ ${\displaystyle {{x\mathrm{}}_{}}_{}}$0 {$displaystyle c_{x_{0}})$인 경우 minL을 반환합니다.그렇지 않으면 c ${\displaystyle {x{}_{}}_{}}$ $(\$을 $반환$합니다.

Delete(Q, x): Queap Q에서 요소 x를 제거합니다.

요소 x의 비트가 1로 설정되어 있으면 요소 L에 격납된다.L부터 T까지 모든 요소를 추가하여 각 요소의 비트를 0으로 설정합니다.각 요소는 2-4 트리의 삽입 조작을 사용하여 T의 오른쪽 끝자녀의 부모에 추가됩니다.L은 비어 있다.자녀가 신규 또는 변경된 모든 노드 v의 h $\$ 포인터를$$ $업데이트$하고 부모가 루트와 같아질 때까지 다음 부모에게 이 프로세스를 반복합니다.루트부터 ${\displaystyle {노드x\mathrm{}}_{}}$ 0$(\$까지 이동하여 $c{\displaystyle {}_{}}$ $\$ 값을$$ 업데이트합니다.k를 n으로 설정합니다.

요소 x의 비트가 0으로 설정되어 있으면 x는 T의 리프입니다.2-4 트리 삭제 조작을 사용하여x 를 삭제합니다.노드 x부터 ${\displaystyle {노드x\mathrm{}}_{}}$ 0$({$으로 이동하여 h ${\displaystyle v_{}}${\$displaystyle h_{v}$ 및$$ ${\displaystyle c_{}}$ v$${\$displaystyle c_{v}$ 포인터를$$ $업데이트$합니다.n과 k를 1씩 감소시킵니다.

Delete Min(Q):Queap Q에서 가장 작은 요소를 삭제하고 반환합니다.

최소(Q) 작업을 실행합니다.작업이 min을 반환합니다.Delete(Q, min) 작업을 실행합니다.최소 반환.

CleanUp(Q): 목록 L 및 트리 T의 모든 요소를 삭제합니다.

목록 L의 첫 번째 요소부터 목록을 트래버스하여 각 노드를 삭제합니다.

트리 T의 루트부터 시작하여 포스트오더 트래버설알고리즘을 사용하여 트리를 트래버스하고 트리 내의 각 노드를 삭제합니다.

분석.

상각분석을 이용하여 실행시간을 분석합니다.Queap Q의 ${\displaystyle \mathrm{잠재적}}$ 함수는 ${\displaystyle (}$ (${\displaystyle }$Q ) ${\displaystyle =}$ ${\displaystyle c}$L ( \ $displaystyle \phi$($$Q ) =$$c L $}$ 입니다$$.$여기$서 Q ${\displaystyle =}$ (${\displaystyle T}$ ,${\displaystyle L}$) { $displaystyle$ Q = ($T$ , $L$) }$$。

삽입(Q, x):작업 비용은 O(1)입니다.리스트 L의 사이즈는 1씩 증가하지만 전위는 일정 c만큼 증가합니다.

최소(Q):이 작업은 데이터 구조를 변경하지 않으므로 상각된 비용은 실제 비용인 O(1)와 동일합니다.

삭제(Q, x):두 가지 경우가 있습니다.

케이스 1

x가 트리 T에 있는 경우 상각된 비용은 변경되지 않습니다.삭제 조작은 O(1) 상각된 2-4 트리입니다.x가 트리에서 삭제되었기 때문에 h ${\displaystyle v_{}}${\$displaystyle h_{$v$$} 및 ${\displaystyle c_{}}$ v$${\$displaystyle c_{v}$ 포인터의$$ $갱신$이 필요할 수 있습니다.최대 O${\displaystyle }$( ${\displaystyle \lg }$q (${\displaystyle x}$)$$\ $displaystyle$O ( $lgq ( x$ ) } )갱신이$$ $있습니다{\displaystyle }$.

케이스 2

x가 목록 L에 있으면 L의 모든 요소가 T에 삽입됩니다.이것은 2-4 트리에 대해 상각된 일정 a의 L$스타일$ a $L)$의 비용이 든다.${\displaystyle h_{}}$ v$${\$displaystyle h_{v}$ $및$ ${\displaystyle c_{}}$v {\$displaystyle c_{$v$$} 포인터 삽입 및 갱신 후 총 소요시간은 ${\displaystyle 2개}$의${\displaystyle }$L(\$displaystyle 2a$ L$\})$로 한정됩니다.두 번째 조작은 T에서 x를 삭제하고 x에서$$(\$displaystyle x_{0$로의 경로를 걸어$hdi$를 $수정$합니다.$splaystyle h_{v}$ $및$ ${\displaystyle c_{}}$ v$${\$displaystyle c_{v}$ 값$$.만약 c입니다. 시간은 대부분의 2는 L+O(나는 gq())){\displaystyle 2a나는 +O(lgq()))}에.;2는{\displaystyle c>, 2a}, 다음amortized가 O(나는 gq())){\displaystyle O(lgq()))}. Delete(Q, x):Minimum(Q)과 Delete(Q, x)의 O(나는 gq())은amortized 비용,)의 추가 낭비되고 있다. {\d$isplaystyle$ O$(lgq(x$

코드 예시

큐의 소규모 Java 구현:

일반의 학급 큐 {     일반의 인트 n, k;     일반의 목록.< >요소> l; // 요소는 일반 데이터 유형입니다.     일반의 큐트리 t;     // Queap용으로 수정된 2-4 트리     일반의 요소 minL;      사적인 큐() {         n = 0;         k = 0;         l = 신규 링크 리스트< >요소>();         t = 신규 큐트리();     }      일반의 정적인 큐 신규() {         돌아가다 신규 큐();     }      일반의 정적인 무효 삽입(큐 Q, 요소 x) {         한다면 (Q.n == 0)             Q.minL = x;         Q.l.더하다(x);         x.리스트 내 = 진실의;         한다면 (x.비교 대상(Q.minL) < > 0)             Q.minL = x;     }      일반의 정적인 요소 최소값(큐 Q) {         // t는 2-4 트리이고 x0, cv는 트리 노드입니다.         한다면 (Q.minL.비교 대상(Q.t.x0.이력서.열쇠) < > 0)             돌아가다 Q.minL;          돌아가다 Q.t.x0.이력서.열쇠;     }      일반의 정적인 무효 삭제(큐 Q, 큐노드 x) {         Q.t.delete Leaf(삭제 리프)(x);         --Q.n;         --Q.k;     }      일반의 정적인 무효 삭제(큐 Q, 요소 x) {         큐노드 n;         한다면 (x.리스트 내) {             // 목록 내 모든 요소의 inList를 false로 설정합니다.             n = Q.t.insert(Q.l, x);             Q.k = Q.n;             삭제(Q, n);         }         또 다른 한다면 ((n = Q.t.x0.이력서).열쇠 == x)             삭제(Q, n);     }      일반의 정적인 요소 최소 삭제(큐 Q) {         요소 분 = 최소값(Q);         삭제(Q, 분);         돌아가다 분;     } } 

「 」를 참조해 주세요.

• 큐(데이터 구조)
• priority 큐
• 스플레이 트리
• 2 ~ 4 트리
• 이중 링크 리스트
• 상각분석

레퍼런스