|\     /|
| )   ( |
| |   | |
( (   ) )
 \ \_/ / 
  \   /  
   \_/   
         

 _   _ 
| \ | |
|  \| |
| . ` |
| |\  |
\_| \_/
       
       

  _____  
 |  __ \ 
 | |  | |
 | |  | |
 | |__| |
 |_____/ 
         
         

         
|\     /|
| )   ( |
| (___) |
|  ___  |
| (   ) |
| )   ( |
|/     \|
         

  _   _ 
 | | | |
 | |_| |
 |  _  |
 |_| |_|
        

IMPORTANT: enter the case-INsensitive alphabetic (no numbers) code AND WRITE SOME SHORT summary of changes (below) if you are saving changes. (not required for previewing changes). Wiki-spamming is not tolerated, will be removed, so it does NOT even show up in history. Spammers go away now.


Visit Preferences to set your user name
Summary of change:
'''Study material for developers''' Heap is a binary-tree data structure stored in an array. The key of the parent is always (kept) smaller or equal to the key of any of its children. Therefore the smallest key element is always at the root of the tree. If you always need the smallest-key element (like the key is a time instant, and you process chronologically) this is a very simple and fast operation. Scientifically speaking insert and delete operations cost is log(n). If you have million elements in a heap, delete or insert operation is just 10 times more time than if you have a few elements. Cool, isn't it? The index of the parent is int(x/2) if x is the index of the child. The root index is 1. (some implementations subtract 1 from indexes, so the root index is 0). See the OnlineCourse/EventQueue for an application of the heap data structure. There is a new proposal from David about a little faster, asm based heap: http://www.squirrelpf.com/msavr/files/asmheap.zip
Optional: Add document to category:
Wiki formatting: * is Bullet list ** Bullet list subentry ... '''Bold''', ---- is horizontal ruler, <code> preformatted text... </code> See wiki editing HELP for tables and other formatting tips and tricks.