• About

Sketches, polytopes

~ Online algorithms, optimization, estimation

Sketches, polytopes

Category Archives: Heaps

Generalized heaps

27 Thursday Oct 2016

Posted by umayrh in Algorithms, Data structures, Heaps, Java, Mathematics

≈ Leave a comment

screen-shot-2016-10-27-at-10-31-39-amMin-max heaps were introduced in [ASSS86] as an efficient way to support heap operations for both minimum and maximum values. Structurally, the min-max heap levels alternate between min-heap condition and max-heap, and hence evaluates grandchildren/grandparents during insertion or search. Min-max heaps can also be generalized to find the k-th smallest element in O(1) time.

Continue reading →

Data structure problems: Heaps and Priority Queues

24 Saturday Jul 2010

Posted by umayrh in Heaps

≈ Leave a comment

1. Heap: in-place sorting using heap in O(n log n).

2. Using heaps to improve merge k lists of size n each in O(n log k) time.

3. How to find the kth smallest element using min-heaps in O(k log k) time.

One solution.

– On various priority queue functions: read.

Aggregation Algorithms Arrays, Lists & Queues Awk BitSet Combinatorics Computational economics Convex geometry Convex optimization Database Data structures First-order methods Graph Theory Heaps Independent sets, cliques, colors Java Linear Algebra Mass deletion Mathematicians Mathematics Number Theory Perl Probabilistic Models & Stochastic Processes Programming Python R Resource allocation Robust Estimation Shell SQL

Blogroll

  • AMS What's Happening
  • IEEE CSS Lectures
  • IMA @ U. Minn.
  • IPAM @ UCLA
  • MOS Optima
  • Proceedings of NAS
  • Quanta
  • R-bloggers
  • SAMSI
  • SIAM News
  • SIGECom Exchanges
  • Simons Institute

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 913 other followers

Follow Sketches, polytopes on WordPress.com
April 2021
M T W T F S S
 1234
567891011
12131415161718
19202122232425
2627282930  
« Aug    

Categories

Blogs I Follow

  • SAMSI Blog
  • Markus Weimer
  • matthew arcus
  • Igor Pak's blog
  • Machinations
  • Karussell
  • Not so Great Ideas in Theoretical Computer Science
  • Abhinav Aggarwal
  • Hydrobates
  • The Operatunist
  • Relax and Conquer
  • Sam Clifford
  • Blog – dstillery
  • A Computer Scientist in a Business School
  • Math ∩ Programming
  • Sketches of Topology
  • Raanan Bar-Cohen
  • Mathematics of Planet Earth
  • AI and Social Science - Brendan O'Connor
  • Adventures in Data Land

Blog at WordPress.com.

SAMSI Blog

Exploring Statistics and Applied Mathematical Research

Markus Weimer

matthew arcus

Igor Pak's blog

Views on life and math

Machinations

Distributed Algorithms and Security

Karussell

Thoughts about Java and more

Not so Great Ideas in Theoretical Computer Science

A student blog of MIT CSAIL Theory of Computation Group

Abhinav Aggarwal

Learn. Master. Innovate.

Hydrobates

A mathematician thinks aloud

The Operatunist

Musings on opera, ballet and theatre

Relax and Conquer

A math research blog by Afonso S. Bandeira

Sam Clifford

Postdoctoral Fellow, Bayesian Statistics, Aerosol Science

Blog – dstillery

Online algorithms, optimization, estimation

A Computer Scientist in a Business School

Online algorithms, optimization, estimation

Math ∩ Programming

Sketches of Topology

visualizations of low dimensional topology

Raanan Bar-Cohen

all about the Partnerships

Mathematics of Planet Earth

Online algorithms, optimization, estimation

AI and Social Science - Brendan O'Connor

Online algorithms, optimization, estimation

Adventures in Data Land

Online algorithms, optimization, estimation

Cancel

 
Loading Comments...
Comment
    ×
    Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
    To find out more, including how to control cookies, see here: Cookie Policy