Every time you write a non-zero-valued word to a location that was previously zero, you pay 20,000 gas. Every time you update a location from one non-zero value to another, you pay 5,000 gas. Writing a zero to a non-zero location gives you a 15,000 gas refund, but only from the gas you're spending in that transaction (i.e. you can't end up with more ether than you started with).
Reading a storage location costs 50 gas, so you'll have to decide whether it's cheaper to use a heap or just read through all your data items. Probably the more items you store, the more worthwhile the heap will be.