AF-heap

In computer science, the AF-heap is a type of priority queue for integer data, an extension of the fusion tree using an atomic heap proposed by M. L. Fredman and D. E. Willard.[1]

Using an AF-heap, it is possible to perform m insert or decrease-key operations and n delete-min operations on machine-integer keys in time O(m + n log n / log log n). This allows Dijkstra's algorithm to be performed in the same O(m + n log n / log log n) time bound on graphs with n edges and m vertices, and leads to a linear time algorithm for minimum spanning trees, with the assumption for both problems that the edge weights of the input graph are machine integers in the transdichotomous model.

See also

References

  1. ^ M. L. Fredman and D. E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Journal of Computer and System Sciences 48, 533-551 (1994)


Stub icon

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

Stub icon

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

Read other articles:

ÖAF

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help to improve this article by introducing more precise citations. (March 2021) (Learn how and when to remove this template message) Österreichische Automobil-FabrikCompany typeSubsidiary of MAN SEIndustryAutomotiveFounded1907HeadquartersFloridsdorf (Vienna), AustriaProductsvehiclesWebsiteOfficial Website ÖAF automobil ÖAF is an initialis...

 

 

Triathlon at the 2014 Central American and Caribbean Games

Triathlon at the 2014 Central American and Caribbean GamesVenueJohn Sparks BoulevardLocationVeracruz, MexicoDates15-16 November← 20102018 → The triathlon competition at the 2014 Central American and Caribbean Games was held in Veracruz, Mexico. The tournament was scheduled to be held from 15–16 November at John Sparks Boulevard. Medal summary Event Gold Silver Bronze Men’s race[1]  Crisanto Grajales (MEX)  Abraham Castellanos (MEX)  ...

 

 

Wat Saket

Wat Saket Ratcha Wora Maha WihanAgamaAfiliasiBuddhismeLokasiNegaraThailandShown within BangkokKoordinat13°45′14″N 100°30′29″E / 13.753864°N 100.508097°E / 13.753864; 100.508097 Gunung Emas Wat Saket Ratcha Wora Maha Wihan (Thai: วัดสระเกศราชวรมหาวิหารcode: th is deprecated , biasanya disingkat menjadi Wat Saket (RTGS: Wat Sa Ket) adalah sebuah kuil Buddhis (wat) di distrik Pom Prap Sattru Phai, Bangkok, Thailand. ...

Nazi Party/Foreign Organization

Foreign Organization branch of the Nazi Party This article is about the original German organization. For the current American organization, see NSDAP/AO (1972). This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (May 2011) (Learn how and when to remove this template message) Nazi Party/Foreign OrganizationNationalsozialistische Deutsche Arbeiterpartei/Auslands-O...

 

 

Brad Friedel

Brad Friedel Informasi pribadiNama lengkap Bradley Howard FriedelTanggal lahir 18 Mei 1971 (umur 52)Tempat lahir Lakewood, Ohio, United StatesTinggi 6 ft 3 in (1,91 m)Posisi bermain Penjaga gawangKarier junior1990–1992 UCLAKarier senior*Tahun Tim Tampil (Gol)1994–1995 USSF 0 (0)1994 → Newcastle United (loan) 0 (0)1995 → Brøndby (pinjaman) 0 (0)1995–1996 Galatasaray 30 (0)1996–1997 Columbus Crew 38 (0)1997–2000 Liverpool 25 (0)2000–2008 Blackburn Rovers 28...

 

 

Dieta di Augusta

Carlo V riceve la Confessio Augustana Le assemblee denominate Dieta di Augusta furono le sedute della Dieta del Sacro Romano Impero avvenute nella città tedesca di Augusta (Augsburg), dal 952 al 1582. Indice 1 Diete di Augusta 1.1 Dieta del 1500 1.2 Dieta del 1518 1.3 Dieta del 1530 («Confessione augustana») 1.4 Dieta del 1547-1548 («Interim di Augusta») 1.5 Dieta del 1550-1551 1.6 Dieta del 1555 (Pace di Augusta) 1.7 Dieta del 1559 1.8 Dieta del 1566 1.9 Dieta del 1582 2 Note 3 Bibliogr...

2013–14 USC Trojans women's basketball team

Intercollegiate basketball season 2013–14 USC Trojans women's basketballPac-12 Tournament ChampionsNCAA Women's Tournament, first roundConferencePac-12 ConferenceRecord22–13 (11–7 Pac-12)Head coachCynthia Cooper-DykeAssistant coaches Brandy Manning Jualeah Woods Evan Unrau Home arenaGalen CenterSeasons← 2012–132014–15 → 2013–14 Pac-12 Conference women's basketball standings vte Conf Overall Team W   L   PCT W   L   PCT No...

 

 

Sankarism

Left-wing ideological trend in Burkina Faso Part of the Politics series onPan-Africanism Arts African art Stolen African art in Western collections Black Star of Africa Pan-African colours Pan-African flag Ideologies African anarchism African communalism African nationalism African philosophy African socialism Afrocentrism Black nationalism Garveyism Négritude Nkrumaism Rastafari Sankarism Third International Theory Ujamaa Organizations African Union Conscious Community Organisation of Afric...

 

 

恩維爾·霍查

恩维尔·霍查Enver Hoxha霍查官方肖像照（摄于1980年代初）阿尔巴尼亚共产党中央委员会总书记任期1943年3月—1948年11月[1]前任無（首任）继任本人（劳动党中央委员会总书记）阿尔巴尼亚劳动党中央委员会总书记任期1948年11月—1954年7月[1]前任本人（共产党中央委员会总书记）继任本人（劳动党中央委员会第一书记）阿尔巴尼亚劳动党中央委员会第一书记任期1954�...

Storm cellar

Type of shelter This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Storm cellar – news · newspapers · books · scholar · JSTOR (April 2011) (Learn how and when to remove this message) A storm cellar on the Texas plains A storm shelter or storm cellar is a type of underground bunker designed to protect the occupa...

 

 

Income in the United States

Overview of the income in the United States of America Overall median household income by state in 2018[1] Income in the United States is measured by the various federal agencies including the Internal Revenue Service, Bureau of Labor Statistics, US Department of Commerce, and the US Census Bureau. Additionally, various agencies, including the Congressional Budget Office compile reports on income statistics. The primary classifications are by household or individual. The top quintile ...

 

 

Castaic Creek

Tributary of the Santa Clara River in California, United States 34°25′10″N 118°37′48″W / 34.41944°N 118.63000°W / 34.41944; -118.63000[1] Castaic CreekCastaic Lake, with Castaic Lagoon and lower Castaic Creek in center-right side.LocationCountryUnited StatesStateCaliforniaRegionLos Angeles CountyPhysical characteristicsSource  • locationLake Hughes Mouth  • locationconfluence with Santa Clara River at C...

Vanity Fair (1998 TV serial)

TV series or program Vanity FairWritten byWilliam Makepeace Thackeray (novel)Andrew DaviesDirected byMarc MundenStarringNatasha LittleFrances GreyPhilip GlenisterTom WardOriginal languageEnglishProductionProducerGillian McneillCinematographyOliver CurtisRunning time300 min. (6 episodes)Original releaseRelease1 November (1998-11-01) –6 December 1998 (1998-12-06) Vanity Fair is a BBC television drama serial adaptation of William Makepeace Thackeray's 1848 novel of the same nam...

 

 

Concordant coastline

Type of coastline created by the folding of differing rock layers parallel to the coast Freshwater Bay, Isle of Wight is an example of an area of concordant coastline - the town of Freshwater is situated on a cove which formed in the hard chalk coastline. In coastal geography, a concordant, longitudinal, or Pacific type coastline occurs where beds, or layers, of differing rock types are folded into ridges that run parallel to the coast.[1] The outer hard rock (for example, granite) pr...

 

 

Mostro della laguna nera

Questa voce o sezione sull'argomento personaggi immaginari non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Gill-ManIl mostro nel film Il mostro della laguna nera UniversoIl mostro della laguna nera Lingua orig.Inglese AutoreHarry Essex 1ª app.1954 – 1956 1ª app. inIl mostro della laguna nera Ultima app. inIl terrore sul mondo...

محمد مفتاح (ممثل مغربي)

  لمعانٍ أخرى، طالع محمد مفتاح (توضيح). تحتاج هذه المقالة إلى الاستشهاد بمصادر إضافية لتحسين وثوقيتها. فضلاً ساهم في تطوير هذه المقالة بإضافة استشهادات من مصادر موثوق بها. من الممكن التشكيك بالمعلومات غير المنسوبة إلى مصدر وإزالتها. (يوليو 2018) محمد مفتاح معلومات شخصية �...

 

 

Stonehall (civil parish)

For other uses, see Stonehall (disambiguation). Civil parish in Leinster, IrelandStonehall Tigh CloicheCivil parishStonehallLocation of Stonehall within County Westmeath in the Republic of IrelandCoordinates: 53°36′37″N 7°19′51″W / 53.61028°N 7.33083°W / 53.61028; -7.33083CountryIrelandProvinceLeinsterCountyCounty WestmeathIrish grid referenceN443625 Stonehall (Irish: Tigh Cloiche)[1] is a civil parish in County Westmeath, Ireland. It is located abo...

 

 

Ghost Child

2013 Singaporean filmGhost ChildTheatrical release posterDirected byGilbert ChanWritten byGilbert ChanTang Fong ChengDanny YeoScreenplay byTan Fong ChengGilbert ChanProduced byGary GohEric KhooTang Fong ChengBert Tan (Executive Producer)StarringChen HanweiJayley WooCarmen SooCinematographyKevin Kee HoeEdited byNatalie SohMusic byKen ChongProductioncompaniesGorylah PicturesClover FilmsMm2 EntertainmentDistributed byGolden Village PicturesRelease date 7 March 2013 (2013-03-07)&#...

Political positions of Donald Trump

Politics of Donald Trump redirect here. Other related information is covered in Political career of Donald Trump and Presidency of Donald Trump. This article is part of a series aboutDonald Trump Business and personal Business career The Trump Organization wealth tax returns Media career The Apprentice bibliography filmography Eponyms Family Foundation American football Golf Honors Public image in popular culture SNL parodies handshakes Legal affairs Sexual misconduct allegations Nicknames p...

 

 

Orso I Participazio

Orso I Participazio Doge VenesiaMasa jabatan864–881 Sunting kotak info • L • B Orso I Participazio adalah Doge Republik Venesia. Doge sendiri adalah jabatan yang dipegang oleh pemimpin Republik Venesia pada masa lampau. Ia mulai menjabat pada tahun 864. Masa kekuasaannya sebagai Doge Venesia kemudian berakhir pada tahun 881. Referensi Norwich, John Julius. A History of Venice. New York: Vintage Books, 1989. ISBN 0-679-72197-5. Pengawasan otoritas Integrated Authority File (Jer...