Kiến trúc máy tính - P12-2

Giả sử rằng mức độ ứu tiên thể hiệnbằng số• Cũng có thể là một đối tượng bất kỳ, nhưngchúng có thể so sánh được với nhau• Giá trị nhỏ nhất có mức ưu tiên caonhất• Các giá trị khác là như nhau
Nội dung trích xuất từ tài liệu:
Kiến trúc máy tính - P12-2Hàngđợiưutiên(PriorityQueues) Sorting 1Cấutrúcdữliệuưutiên• Giảsửrằngmứcđộứutiênthểhiện bằngsố Cũngcóthểlàmộtđốitượngbấtkỳ,nhưng • chúngcóthểsosánhđượcvớinhau• Giátrịnhỏnhấtcómứcưutiêncao nhất Cácgiátrịkháclànhưnhau • Sorting 2Hàngđợiưutiên(Priorityqueue) Làcấutrúcdữliệuchoviệclưutrữmọttập cácphầntửcóionofprioritizedelements Hỗtrợchènthêmphầntửbấtkỳ Hỗtrợloạibỏphầntửvớimứcưutiêncao nhấttạibấtkỳthờiđiểmnào. Khôngnhưnhữngcấutrúcdữliệudựatrên địachỉ(stacksqueues)vìnókhôngđịnh nghĩavịtríchongườisửdụng Sorting 3Càiđặt Bằngdanhsách–Đơngiảnnhưng khônghiệuquả Bằngcâyheap–hiệuquảhơn(thời gianyêucầulàhàmlog) Sorting 4HàngđợiưutiênADT Mộthàngđợiưutiênlưutrữ Thêmvàomộtsốphương mộttậpcácphầntử thức Mỗiphầntửlàmộtcặp min()  trảlạiphầntửcókhóanhỏ (key,value) nhấtnhưngkhôngloạibỏnó Cácphươngthứcchínhcủa đi HàngđợiưutiênADT size(),isEmpty()  insert(k,x)  Chènmộtphầntửvớikhóa kvàgiátrịx Cácứngdụng: removeMin()  Loạibỏvàtrảlạiphầntửcó Cácmáybaydựphòng  khóanhỏnhất Đấugiá  Thịtrườngchứngkhoán  (Stockmarket) Sorting 5Quanhệthứtựtoànphần Cáckháiniệmtoánhọc Cáckhóatronghàng vềquanhệthựtự≤ đợiưutiêncóthểlà cácđốitượngbấtkỳ toàn phần vàtrênnóđượcđịnh T/cphảnxạ:  nghĩamộtthứtự x≤ x Haiphầntửphânbiệt T/cphẩnđốixứng:  x ≤ y∧y ≤ x ⇒x = y trongmộthàngđợi ưutiêncóthểcó T/cbắccầu:  x ≤ y∧y ≤ z ⇒x ≤ z khóagiốngnhau Sorting 6PhầntửADT(§7.1.2) Mộtphầntửtronghàng CàiđặttrongC++ đợiưutiênđơngiảnlà template classEntry{ Hàngđợiưutiênlưutrữ private: cáccặpchophépthêm Object1value; vàovàloạibỏđidựa Object2key; trêncáckhóa. public: Cácphươngthức: Objectkey(); key():trảlạigiátrịkhóa  Objectvalue(); củaphầntử }; value():trảlạigiátrịcủa  phầntử Sorting 7ToántửsosánhADT(§7.1.2) Acomparatorencapsulates theactionofcomparingtwo objectsaccordingtoagiven totalorderrelation Theprimarymethodofthe Agenericpriorityqueue ComparatorADT: usesanauxiliary comparator compare(x,y):Returnsan  Thecomparatorisexternal integerisuchthatib;anerroroccursifaandb Whenthepriorityqueue cannotbecompared. needstocomparetwokeys, itusesitscomparator Sorting 8ExampleComparator Lexicographiccomparisonof2D points: Pointobjects:/**Comparatorfor2Dpointsunderthe /**Classrepresentingapointinthe standardlexicographicorder.*/ planewithintegercoordinates*/publicclassLexicographicimplements publicclassPoint2D { Comparator{ protectedin ...