Providing increased capacity in heterogeneous storage elements including a method for storing data in a heterogeneous memory that includes receiving a write message and a write address corresponding to a block of memory cells where at least two of the memory cells support different data levels, determining physical characteristics of the memory cells, and identifying virtual memories associated with the block of memory cells in response to the physical characteristics. The following is performed for each of the virtual memories: generating a constraint vector that describes the virtual cells in the virtual memory; and calculating a virtual write vector in response to the constraint vector and the write data, the calculating including writing the write data, bit by bit, in order, into the virtual memory, skipping locations known to be stuck to a particular value as indicated by the constraint vector. The virtual write vectors are combined into a write word and the write word is output to the block of memory cells.